【手撕数据结构】卸甲时/空间复杂度

前言

要想知道什么是空/时间复杂度,就得知道什么是数据结构。

这得分两层来理解。我们生活中处处存在数据，什么抖音热点上的国际大事，什么懂的都懂的雍正卸甲等等一系列我们用户看得到的，就是抖音存储在后台服务器的数据。但这些数据都有一个特点，那就是都在抖音的热搜榜单上，而这个榜单就是结构，保证数据在一个固定的位置里以便用户浏览。

此外有了数据结构，就离不开算法。那么我们刚刚说了，数据结构是把数据有规律的存储在一个结构中，那么怎么从结构中有效率的存取数据，这就是算法。

时间复杂度

有了算法，就存在时间复杂度和空间复杂度。因为计算机现在的内存越来越大，所以时间复杂度比空间复杂度更显得重要。所以我们先来了解时间复杂度

概念

时间复杂度，最重要的词就是时间，这里的时间就是指一个程序运行时的时间，如果时间复杂度越少，那么证明这个算法越好。时间复杂度计算用函数式T(N)表示

那为什么我们不提前算出这个程序的时间复杂度来写出最优解的代码呢？这里就涉及到计算机的问题。

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译
   器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

下面我们来看一段代码:

// 请计算⼀下Func1中count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}

这段代码如果根据count的执行次数来看的话应该是:
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

这时候有人就说，那个int count=0不算吗;

这里我们就太小看我们的计算机了，我们计算机一秒钟cpu可以执行上亿次，这小小的一次当然可以忽略不计。所以说我们计算的时间复杂度并不准确，只是粗略估计而已，这时候我们就用一个新的符号表示.

⼤O的渐进表⽰法

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号;这里用来表示估算的时间复杂度。

那么这里还是跟T(N)一样算吗，如果是这样我们就没必要用另外一个符号来表示了。这里就涉及到算O的规则:

1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了
3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

那么再来看上面的T(N)=N^ 2 + 2 ∗ N + 10,这里的最高阶是N2所以去掉其他的低阶，复杂度就为(ON^2)

小试牛刀

// 计算Func3的时间复杂度？
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);
}

这里的T(N)=M+N，那我们再来算O(N),这里M和N都是同阶，所以不符合第一条规则，也没有对应第二条和第三条，所以为o(N+M)，那么有人就问了，万一N比M大呢，是不是因该是O(N).这里问题就是，你怎么知道N比M大？万一是M比N大呢，所以保险起见我们都留下来。

// 计算strchr的时间复杂度？
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;
}

这里我们是查找character在str中的位置，这里我补充一个知识点:

• 我们的O算的一般是一个算法的最坏情况下的复杂度
  这里就可以分为三个复杂度:
  1.最好情况
  若要查找的字符在字符串第⼀个位置，则：
  F (N) = 1,复杂度为o(1)

2.平均情况:
若要查找的字符在字符串中间位置，则：
F (N) = N/2,O(N/2)

3.最坏情况
若要查找的字符在字符串最后的⼀个位置，则：
F (N) = N,O(N)

// 计算BubbleSort的时间复杂度？
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;
}
}

最坏情况下，又因为保留高阶去掉n/2(第一条),忽略系数(第二条)，所以为ON^2

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

当n=2时，执⾏次数为1
当n=4时，执⾏次数为2
当n=16时，执⾏次数为4
假设执⾏次数为 x ，则 2
x = n
因此执⾏次数： x = log n
因此：func5的时间复杂度取最差情况为：
O(log2 ^n)

不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n

空间复杂度

空间复杂度要注意的是，他的计算表示也是用O来表示，并且他的规则与时间复杂度一样遵守那三条规则

注意

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

例1:

// 计算BubbleSort的时间复杂度？
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;
}
}

函数栈帧在编译期间已经确定好了，
只需要关注函数在运⾏时额外申请的空间。
BubbleSort额外申请的空间有
exchange等有限个局部变量，使⽤了常数个额外空间
因此空间复杂度为 O(1)