「时间复杂度」

前言

前言：复杂度分析是数据结构与算法绕不开的话题。

一、什么是时间复杂度

时间复杂度，计算的是程序（代码）运行所花费的时间。 但是，同一个程序在不同电脑上运行的时间也是不同的，因为不同电脑的性能不同。 所以，一般说的时间复杂度并不是真正的代码运行的时间，而是一个程序中代码所运行的次数。将这个次数写成一个数学函数表达式，此时这个表达式就是此程序（代码）的时间复杂度。

二、大O渐进表示法

1、大O表示法的方式

• 仅保留最高项；
• 最高项的次数为 1；
• 当代码的运行次数为常数时，统一记为 O(1)；

2、示例解释

1）O(n)

#include <iostream>
using namespace std;
int main()
{
 int n;  // 运行次数为1
 cin >> n;  // 运行次数为1
 
 for(int i=0; i < n; i ++)
 {
  printf("%d ", i); // 运行次数为n
 }
 
 int m = 10;  // 运行次数为1
 
 while(m --)
 {
  printf("Hello World\n");  // 运行次数为10
 }
 
 return 0;
}

整个程序的运行次数为 n + 13，运行次数函数表达式 F(n) = n + 13，大 O 表示法记作 O(n)。

2）O(n^2^)

void Func(int n)
{
 int count = 0;  // 执行次数为1
 
 for(int i =0; i < n; i++)  // 总执行次数为n*n
 {
  for(int j = 0; j < n;j++)
  {
   count ++;
  }
 }
 
 for(int k = 0; k < 2 * n; k++)  // 执行次数为2n
 {
  count ++;
 }
 
 int m = 10;  // 执行次数为1
 
 while(m --)  // 执行次数为10
 {
  count ++;
 }
 
 cout << count << endl;  // 执行次数为1
}

整个程序的运行次数为 nn + 2n + 13，运行次数函数表达式 F(n) = nn + 2n + 13，大 O 表示法记作 O(n^2^)。 假设， n = 10 时，F(n)=133； n = 100 时，F(n) = 10213; n = 1000 时，F(n) = 1002013; 随着 n 的增大，n*n 的占比越大，只需要保留该函数表达式中的最高次项，剩余项可以完全忽略。 上述程序的运行次数函数表达式可以简化为：O(n^2^)。

3、最坏情况、最好情况、平均情况

有些时候，算法运行的次数是不确定的。例如，利用遍历方式在长度为 n 的数组中寻找一个数字。 a、最好的情况，我们要找的数字正好是数组第一个元素，此时算法的时间复杂度为 O(1)； b、最坏的情况，我们要找的数字正好是数组的最后一个元素，此时算法的时间复杂度为 O(n)； c、在最好和最坏情况间取平均值，即 n/2，利用大 O 表示法时，省略最高项系数，时间复杂度仍为 O(n)； 总结：算法的时间复杂度可分为三种情况

• 最坏情况：任意输入规模的最大运行次数（上界）；
• 平均情况：任意输入规模的期望运行次数；
• 最好情况：任意输入规模的最小运行次数（下界）；

三、常见的时间复杂度分析

1、O(1)

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

2、O(n)

void f(int n)
{
 int count = 0;
 for (int k = 0; k < 2 * n; ++ k)
 {
  count ++;
 }
 
 int m = 10;
 while (m --)
 {
   count ++;
 }
 printf("%d\n", count);
}

3、O(log n)

不管是以 几为底，把所有对数阶的时间复杂度都记为 O(logn)。

int i = 1;
while (i <= n) {
 i = i * 2;
}

4、O(m + n)

m 和 n 表示两个数据规模。

void f(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);
}

5、O(n^2^)

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