数据结构--时间/空间复杂度

一. 时间复杂度

• 时间复杂度简单的说就是一个程序运行所消耗的时间，叫做时间复杂度，我们无法目测一个程序具体的时间复杂度，但是我们可以估计大概的时间复杂度。
  
• 一段好的代码的就根据算法的时间复杂度，即使在大量数据下也能保持高效的运行速率，这也是我们学习算法的必要性。
  

1.1 大O表示法

我们来看看下面这代码的时间复杂度

1. void Func1(int N)
2. {
3.     int count = 0;
4.     for (int i = 0; i < N; ++i)
5.     {
6.         for (int j = 0; j < N; ++j)
7.         {
8.             ++count;
9.         }
10.     }
11.     for (int k = 0; k < 2 * N; ++k)
12.     {
13.         ++count;
14.     }
15.     int M = 10;
16.     while (M--)
17.     {
18.         ++count;
19.     }
20.     printf("%d\n", count);
21. }

复制代码

这个函数在调用的过程中使用了三个for循环和一个while循环，每循环一次我们说它进行了一次基本操作。那么这个函数执行基本操作的次数为F(N)=N²+2*N+10

• 推导大O阶方法：
  
  
  
  • 用常数1取代运行时间中的所有加法常数。
    
  • 在修改后的运行次数函数中，只保留最高阶项。
    
  • 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
    
  
  
• 按照上面的规则，那么上述代码的时间复杂度就为O(N²)。
  
• 我们发现，通过上面的规则，我们就使用N²来代替了N²+2*N+10，我们为什么要这样规定呢，我们以上面的表达式为例，当N为不同的值时，表达式的结果为多少
  

1. eg:
2. N=100 F(N)=10210
3. N=1000 F(N)=1002010
4. N=10000 F(N)=100020010

复制代码

我们发现，当N不断变大时，表达式的值也不断变大，而对表达式的结果影响最大的一项就是这个表达式中阶数最高的那一项。
二. 空间复杂度

• 简单的说就是程序运行所需要的空间。
  
• 写代码我们可以用时间换空间，也可以用空间换时间。加大空间消耗来换取运行时间的缩短加大时间的消耗换取空间，我们一般选择空间换时间。一般说复杂度是指时间复杂度。
  

2.1 空间复杂度的定义

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
我们以冒泡排序举例：

1. void BubbleSort(int* a, int n)
2. {
3.      assert(a);
4.      for (size_t end = n; end > 0; --end)
5.      {
6.          int exchange = 0;
7.          for (size_t i = 1; i < end; ++i)
8.          {
9.              if (a[i-1] > a[i])
10.              {
11.                  Swap(&a[i-1], &a[i]);
12.                  exchange = 1;
13.              }
14.          }
15.          if (exchange == 0)
16.          break;
17.      }
18. }

复制代码

根据定义我们知道，空间复杂度是用来估算占用空间的大小的，那么我们就可以根据算法中创建的变量的个数来表示算法的空间复杂度，这个冒泡排序算法创建了3个变量，根据大O的渐进表示法的规则，该算法的空间复杂度就为O(1)。
我们在以斐波那契数列为例：
[code]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