夯实数据结构和算法系列（一）---复杂度分析

1. 解决的问题：

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何使程序 加节省存储空间.

2. 大 O 复杂度表示法：

eg：求1,2,3,4…,n的累加和，估算这段代码的执行时间：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

分析：
从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据---运算--- 写数据。尽管每行代 码对应的 CPU执行的个数和时间都不一样，但是这里只是粗略的估计，所以假设每行代码执行的时间都一样，为unit_time.则：

第 2,3 行代码分别需要1个uint_time，第 4、5 行都运行了 n 遍，所以需要
2 n * unit_time 的执行时间。所以这段代码的执行总时间 T(n)= (2n+2)*unit_time。

eg:

 int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }

分析：
第2,3,4行，每行代码执行时间为unit_time,第5,6行执行了 n 遍，故执行时间为 2nunit_time，第 7 8 行也执行了n遍，执行时间为：2n^2unit_time。

故该段代码执行的总时间为：T(n)=(2n^2+2n+3)*unit_time.

综上得：所有代码的执行时间 T(n) 与执行次数 n成正比

image

• T(n)表示代码执行的时间

• n 表示数据规模的大小
• f(n) 表示每行代码执行的次数的综合
• O 表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

所以，第一个例子中的 T(n) = O(2n+2)，第二个例子T(n) = O(2n2+2n+3)。这就是大 O 时间复杂度表示。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫“渐进时间复杂度”，简称“时间复杂度”

3. 时间复杂度分析

• 只关注循环执行次数最对的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

• 几种常见的时间复杂度实例分析

image

(1) O(1)

image

(2) O(logn)、O(nlogn)

image

5. 空间复杂度

空间复杂度全程：渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

eg:

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

分析:
可以看到：第2行中，我们申请了一个空间存储变量 i，但它是常量阶，跟数据规模 n 无关，第3行申请了大小为 n 的int 型数组，除此之外，剩下的代码并没有占用更多的空间，故整段代码的空间复杂度为 O(n).

image image