数据结构入门之复杂度
前言：终于来到了数据结构。要想学好数据结构，首先就要了解数据结构的复杂度。那么，什么是复杂度呢？
1 数据结构
所谓数据结构（Data Structure）就是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
算法（Algorithm）：就是定义良好的计算过程，它取一个或一组的值为输入，并产生出一个或一组的值为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
那么如何来衡量一个算法的好坏呢？
2 复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
2.1 时间复杂度
定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量的描述了算法的运行时间。时间复杂度是衡量程序的时间效率，那为什么不去计算程序的运行时间呢？
原因有以下几点：
1.程序运行时间和编译环境，运行机器的配置都有关系。在同样的机器不同的编译器上运行时间也可能有所不同。
2.同一个算法程序在不同的机器上运行时间也会有所不同。
3.并且时间只能在程序写好后测试，不能写程序前通过理论思想计算评估。
那么函数式T(N)到底是什么呢？这个T(N)函数式计算的是程序的执行次数。假设计算机每条指令执行的时间基本一样（实际中有差别，但是差别不大），那么执行次数和运行时间成正相关。执行次数就可以代表程序时间效率的优劣。
#include<stdio.h>
#include<time.h>
int main()
{
time_t ret1 = time(NULL);
int arr[100000] = { 6,4,8,2,9,1,7,3,10,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < sz - 1; i++)
{
for (int j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
time_t ret2 = time(NULL);
printf("%lld\n", ret2 - ret1);
return 0;
}
这段代码就很好的证明了上述观点。程序每次运行起来获取的时间不一定是一样的。接下来就是习题大集合。来看看下面代码的复杂度吧。
// 请计算⼀下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;
}
}
实际在计算时间复杂度时，计算的并不是程序执行的准确次数（这样做的意义也不大）。所以我们只需要计算程序执行的大概次数就可以了。复杂度的表示通常使用大O的渐进表示法。
2.2 大O的渐进表示法
大O渐进表示法的规则
1.时间复杂度函数式T(N)中，只保留最高阶项，去掉低阶项。
因为N不断变大时，低阶项对结果影响越来越小，当N无穷大时，
就可以忽略不计了。
2.如果最高阶项存在且不是1，则去除这个项的系数。因为当N
不断变大时，这个系数对结果的影响越来越小，当N无穷大时，
就可以忽略不计了。
3.T(N)中如果没有N相关的项，只有常数项。则用常数1代替。
所以，上述Func1代码的时间复杂度是O(N^2)。
接下来的代码时间复杂度又是多少呢?
// 计算Func2的时间复杂度？
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);
}
根据大O的渐进表示法，Func2的时间复杂度是O(N)。
// 计算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);
}
Func3的时间复杂度分为三种情况：
1.M>>N，Func3的时间复杂度是O(M)
2.M<<N，Func3的时间复杂度是O(N)
3.M与N近似相等，Func3的时间复杂度是O(N)或O(M)
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
// 计算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;
}
总结：
最坏情况：任意输入规模的最大运行次数（上界）
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数（下界）
大O的渐进表示法在实际中一般情况关注的是算法的上界，也就是最坏运行情况
// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = 0; end < n - 1; ++end)
{
int exchange = 0;
for (size_t i = 0; i < end - i - 1; ++i)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
因此，BubbleSort的时间复杂度是O(N^2)。
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if (0 == N)
{
return 1;
}
return Fac(N - 1) * N;
}
2.3 空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行期间因为算法的需要额外临时开辟的空间。空间复杂度并不是程序占用多少个Bytes的空间，因为常规情况下每个对象的大小差异不会很大，所以空间复杂度计算的是变量的个数。
空间复杂度也使用大O的渐进表示法。
注意：函数运行时所需要的栈空间在编译期间就已经确定好了，因此空间复杂度主要通过函数在运行时显示申请的额外空间来确定。
// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = 0; end < n - 1; ++end)
{
int exchange = 0;
for (size_t i = 0; i < end - i - 1; ++i)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
BubbleSort函数所需要的栈空间在编译期间就已经确定好了，只需要关注函数在运行时所需要申请的额外空间。BubbleSort额外申请的空间有end,exchange等有限个局部变量，使用了常数个空间，因此BubbleSort空间复杂度是O(1)。
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
Fac递归调用了N次，开辟了N个栈帧空间，每个栈帧使用了常数个空间，因此空间复杂度为O(N)。
3 常见复杂度对比
