一起学数据结构（1）——复杂度

目录

1. 时间复杂度：

1.1 时间复杂度的概念：

1.2 时间复杂度的表示及计算：

1.3 较为复杂的时间复杂度的计算：

2. 空间复杂度：

2.1 空间复杂度的概念：

2.2 空间复杂度的计算：

---

1. 时间复杂度：

1.1 时间复杂度的概念：

        时间复杂度是一个函数，用于衡量一个算法的运行快慢，对于一个算法而言，在不同配置上的机器运行的速度是不一样的，所以，并不能简单的用运行的时间来衡量算法的运行快慢。虽然用时间来表示并不合理，但是，一个算法运行的时间与这个算法中基本操作的次数成正比，所以，将一个算法中的基本操作的运行次数定义为时间复杂度。

1.2 时间复杂度的表示及计算：

       上面给出了时间复杂度的概念后，这里给出一个例子：

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的渐进表示法 ，对于上述代码，可以表示为O(N^2).

对于时间复杂的的计算，在不同的情况下有不同的规则，下面通过举例来引出这些规则:

例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);

按照上面所说的方法，用函数来表示上述代码中基本操作的运行次数，即：

                                                  

取函数中有决定性因素的项，即：，不过在用大O的渐进法进行表示时，在N的前面存在一个常数，需要满足用常数1取代运行时间中的所有加法常数这个规则，所以，时间复杂度表示为O(N).

例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);

此时的时间复杂度为：，因为不能分辨，M、N二者的大小，所以也就不能分辩二者谁在时间复杂度中起决定性作用。 

  如果给出的条件足以分别二者之间的大小关系：

 当时，时间复杂度可以表示为：

当时，时间复杂度可以表示为：

当时，时间复杂度可以表示为；或者

例3：

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

对于例3所给出的代码，执行次数为100次，并不是一个函数式，对于这种只有常数的类型，用来表示。 

例4：

const char * strchr ( const char * str, int character );

strchr函数的功能实在一个字符串中，寻找和某个目标字符相同的字符。假设，字符串的长度为N，查找的次数表示为K对于在这个字符串中查找目标字符，可以分为三种情况：

 第一种情况： 第一次就找到目标字符，执行次数为1.

第二种情况：在时找到目标字符。

第三种情况： 最坏的情况，即时找到目标字符。

对于这种多情况的代码的时间复杂度，按照最坏的情况进行表示，所以，例4的时间复杂度为。

在了解了时间复杂度的基本运算规则即表示后，下面引入一些较为复杂的时间复杂度的计算：

1.3 较为复杂的时间复杂度的计算：

  例1：

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){(a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}
if (exchange == 0)
break} 
}

对于例1，即冒泡排序的复杂度的计算：需要注意，当有循环嵌套时，时间复杂度的计算应按照累加，而不是累乘，对于冒泡排序，可以理解为，共有N中情况，每种情况中代码的基本操作的执行次数一次为,即满足一个等差数列。但是需要注意，冒泡排序的执行次数依旧有三种情况，假设代码的执行次数为K:

   第一种情况：最好的情况，给定的数组有序。此时

   第二种情况：

   第三种情况：最坏的情况，此时

通过前面对时间复杂度的介绍，可以得出，冒泡排序的时间复杂度为：

例2：

int BinarySearch(int* a, int n, int x) 
{assert(a);int begin = 0;int end = n-1;
// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end-begin)>>1);if (a[mid] < x)begin = mid+1;else if (a[mid] > x)end = mid-1;elsereturn mid;}
return -1;

对于二分查找的时间复杂度的计算： 假设，数据的总量为N，每次查找后，数据的总量会/2，也就是说，查找K次后的数据总量为,对于二分查找而言，最坏的情况就是查找K次后,

此时，K和N的关系可以表示为 (注：此时的log以2为底）。由于文本编辑的原因，以2为底的对数不容易编写，所以，将以2为底的对数写成,对非2为底的对数不成立！

例3：

long long Fac(size_t N)
{if(0 == N)return 1;
}return Fac(N-1)*N;
}

对于递归算法，其时间复杂度是多次调用的代码的次数的累加，所以，对于例3给出的递归，调用的次数最大是次，所以，时间复杂度是。

如果，对于例3中的代码做一点简单的修改，即：

long long Fac(size_t N)
{if(0 == N)return 1;
}for( size_t i = 0; i < N; i++){.......}return Fac(N-1)*N;
}

与例3不同的是，在例3中的最后一行代码表达的意思就是递归运算后的结果×，时间复杂度只与递归的调用次数有关，对于递归后面×的N，只是对结果进行乘法。

但是，在这个例子中，递归的次数一共是次，但是，在每次递归的时候，中间会有一个循环，所以，代码一共会递归次，但是，每次在递归中，循环的次数是次，前面说到对于递归算法的时间复杂度，是多次调用的代码的次数的累加，并不是类乘，因此，对于次代码整体的逻辑可以理解为一个等差数列，时间复杂度为

例4：

long long Fib(size_t N)
{if(N < 3)return 1;
}return Fib(N-1) + Fib(N-2); 
}

例4是一个双动递归，对于这种递归的时间复杂度的运算，由下面的一张图来表示：

 如图所示是参数为5时的调用情况。如果，当参数为时，调用情况会变成下图所示：

稍加观察会发现，图中每一行的项的个数都满足的数量。再结合上面的图像不难得出一个结论，如果按照图中的计算方法一直进行下去，右边数据到达的速度大于左边，所以，当所有的项都变成时，图形的结构可以用下面的图片表示：

其中白色和蓝色的交界处表示此时递归变成了 。蓝色部分表示下面没有项，所以，当蓝色部分出现后，每一行的元素数量不再严格的满足.但是，当很大是，即使缺少了一部分，此时所有项之和的数量级，依旧和类似，在此处也可以理解为，三角形项的和的极限无限趋近于。 所以，对于上面给出的递归，其时间复杂度为

2. 空间复杂度：

2.1 空间复杂度的概念：

   在介绍时间复杂度的概念时说过，时间复杂度是一个函数表达式，同样，对于空间复杂度来说也是一个函数表达式 ，对算法运行过程中临时占用存储空间大小的量度。但是对于空间复杂度，并不是指程序占用了多少bytes的空间，空间复杂度针对的目标是变量的个数。

2.2 空间复杂度的计算：

对于空间复杂度的计算，依旧通过给出例子来计算不同情况下的空间复杂度：

例1：

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;}}

还是拿冒泡排序举例，在计算时间复杂度时，最后得出冒泡排序的时间复杂度是。

对于冒泡排序时间复杂度的计算，通过上面给出的概念，可以知道，时间复杂度针对的对象是代码中临时占用内存空间的变量，可以理解为，为了解决某个问题或者为了完成代码而创建的变量，对于上面的代码，可以看出，为了完成冒泡排序，创建了三个变量分别是。所以，上述代码中临时占用内存空间的变量的数量为3，所以，冒泡排序的空间复杂度为。

例2：

long long* Fibonacci(size_t n)
{if(n==0)return NULL;long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; ++i){fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}
return fibArray；

例2中，为了完成代码，所以，利用动态内存函数malloc创建了个临时占用空间的变量。下面虽然也创建了变量i,但是，空间复杂度仍然是取起决定性作用的值，所以，例2的空间复杂度为。

例3：

long long Fac(size_t N){{if(N == 0)return 1;}return Fac(N-1)*N;}

对于递归而言，每次运算都要开辟常数量的空间，需要开辟次，所以，空间复杂度为。

例4：

long long Fib(int N)
{{ if(N < 3)return 1;}return Fib(N-1) + Fib(N-2);
}

在计算双动递归的空间复杂度之前，需要了解一个概念，及：时间是累加的，空间是可以重复利用的。对于这句话和求双动递归的空间复杂度有什么关系，可以用计算双动递归的时间复杂度的图来解释：

 图反应的只是双动递归执行的大体结构，但是，不反应双动递归运行时的顺序，对于双动递归运行时的顺序，是。当运行后，加上所占用的空间，可以看成一共占用了5个内存空间。返回,此时所占用的内存空间还给操作系统，下次执行时，再执行,但是对于的使用，并不会再开辟一个新的内存空间，而是将还给操作系统的空间再给使用，这也就对应了上面的话：空间是可以重复利用的。对于其他元素，同样出现重复利用内存空间的情况。所以，计算双动递归的空间复杂度时，计算的应该是递归一直向下执行时（即不出现上面所说的重复利用空间的情况）所占用内存的最大值，所以，对于,向下执行时所占用内存空间的最大值为。因此，双动递归的空间复杂度为。