算法的复杂度

1.数据结构前言

下面的概念有的比较难理解，做个了结就行。

1.1数据结构的起源

在现实生活中我们更多地并不是解决数值计算的问题，而是 需要一些更科学的手段如（表，数，图等数据结构），才能更好地处理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。

1968年，美国高德纳教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中，较系统的阐述了数据的逻辑结构及其操作。

1.2数据结构（Data Structure）的定义

数据结构：相互之间存在一种或者多种关系的数据元素的集合

数据元素：是组成数据的，有一定意义的基本单位，在计算机中被当做成体处理。也叫做记录。比如在人类社会中，它的数据元素就是人。畜类中，牛羊猪等就是它的数据元素。

数据项：一个数据元素可以由多个数据项组成。比如人的数据项可以由眼睛、鼻子、嘴巴等等。

数据对象：具有相同性质的数据元素的集合，是数据的子集。比如人都有生日、姓名、性别，把这些拥有相同数据项的数据元素就称为相同性质的数据元素。

1.3逻辑结构与物理结构

1.3.1逻辑结构

逻辑结构：数据元素之间的相互关系。

常见的逻辑结构：

集合结构：（”平等“）

线性结构：（一对一）

树形结构：（一对多）

图形结构：（多对多）

1.3.2物理结构

物理结构：指的是数据的逻辑结构在计算机中的存储方式

存储结构的分类：顺序存储结构、链式存储结构

顺序存储结构：把数据元素存放在连续的内存空间中，这种的结构的物理结构与逻辑结构是相同的

链式存储结构：把数据元素存放在任意的内存空间中，这个任意可以连续也可以不连续。

这种存储结构的操作是建立在指针域上的，因为你总得通过一个手段去找到这些元素。

1.4抽象数据类型

1.4.1数据类型

数据类型：只一组具有相同性质的值的集合以及定义在此集合上面的一组操作的总称。

高级语言中，类型往往指代的是变量、常量、表达式所能表示的范围，还有所能进行的+ - * /等一系列操作。

在C语言中，数据类型分为：

原子类型：不可再分的基本单位，包括整形、浮点型、字符型

结构类型：由若干个类型组合而成，可以再分。比如：一个整形数组就包含若干个整形数据。

1.4.2抽象数据类型

抽象是指抽出事物具有的本质属性。

抽象数据类型：是指一个数学模型以及定义在该模型上面的一组操作。

对于抽象数据类型，我们并不关注数据本身的物理结构，而是关注它的数学抽象特征。

一个抽象数据类型定义了：一个数据对象、数据元素中各数据元素之间的关系及对数据的操作。

2.算法的复杂度

在次之前我们先看一个例题：189. 轮转数组 - 力扣（LeetCode）

经过考虑我们可以有三种解法：

1.挨个轮转

void rotate(int* nums, int numsSize, int k) {int i=0;while(k--){int tmp=nums[numsSize-1];for(i=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=tmp;}
}

2.取余挨个轮转：

void rotate(int* nums, int numsSize, int k) {int i=0;k%=numsSize;while(k--){int tmp=nums[numsSize-1];for(i=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=tmp;}
}

3.面向结果编程：

void rotate(int* nums, int numsSize, int k) {int ans[numsSize];int i=0;for(i=0;i<numsSize;i++){ans[(i+k)%numsSize]=nums[i];}for(i=0;i<numsSize;i++){nums[i]=ans[i];}}

4.三次逆序法：

void Reverse(int* nums,int low,int high){while(low<high){int tmp=nums[low];nums[low]=nums[high];nums[high]=tmp;low++;high--;}
}
void rotate(int* nums, int numsSize, int k) {k%=numsSize;Reverse(nums,0,numsSize-k-1);Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-1);}

2.1时间复杂度

先说明一下：上述方法的1、2的关系为优化。3、4是使用了不同的算法。

2.1.1时间复杂度的定义

时间复杂度：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T(n)数量级。算法的时间复杂度，也就是算法的时间量度，记作T(n)=O(f(n))。它表示随着问题规模n的增大，算法的执行时间的增长率和符f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中符f（n）是问题规模n的某个函数。

这里我们从定义中提取几个关键点：

1.算法时间复杂度是算法渐进时间复杂度的简称。

2.它表示的是一种变化趋势（随问题规模）或者增长率。

3.并不是一个确切的语句到底执行多少次的函数表达式。

2.1.2算法时间复杂度的大O渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

💡 推导⼤O阶规则

1. 时间复杂度函数式 T(N) 中，只保留最⾼阶项，去掉那些低阶项，因为当 N 不断变大时，

低阶项对结果影响越来越小，当 N 无穷大时，就可以忽略不计了。

2. 如果最高阶项存在且不是 1 ，则去除这个项目的常数系数，因为当 N 不断变大，这个系数

对结果影响越来越小，当 N 无穷大时，就可以忽略不计了。

3. T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。

2.1.3算法时间复杂度的例题：

2.1.3.1

void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}

T（n）=2*n+10（只关注循环的额外开销）

时间复杂度：O(n)

2.1.3.2

void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%d\n", count);
}

同样的时间复杂度：O(n)

2.1.3.3

void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

O(1)

2.1.3.4

const char * strchr ( const char
* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}

这是一个查找某个字符的算法，但是不同情况有不同的复杂度有不同划分：

假设要找的就在第一个字符位置（或常数个）：T(n)=k(常数) --> O(1)4

假设要找的在最后一个位置：T(n)=n --> O (n)

假设要找的在中间：T(n)=n/2 --> O(n)

2.1.3.5

void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

T(n)=N*(N+1)/2 -->O(n)=n^2

2.1.3.6

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}

O(n)=logn  这里写成lnn lgn都行，因为我们说时间复杂度表示的是变化率，所以只需要表示出来对数阶就可以。

2.1.3.7

递归的时间复杂度

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

O(n)=n

递归时间复杂度的求法=单次递归的时间复杂度*递归次数

2.1.4常见的时间复杂度

2.2.空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

当不加限定的说复杂度时一般指代的是时间复杂度，所以空间复杂度的讨论并不会很深入。

例题：

void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

由于额外开辟的空间仅是几个常量所以空间复杂度为O(1)

3.轮转数组复杂度分析

法一：O(n^2)    O(1)

法二：O(n^2)    O(1)

法三：O(n)       O(n)

法四：O(n)       O(1)

完