算法复杂度代码示例

一、算法复杂度及代码运行步骤

确定决定算法运行时间的组成步骤。
找到执行该步骤的代码，标记为 1。
查看标记为 1 的代码的下一行代码。如果下一行代码是一个循环，则将标记 1 修改为 1 倍于循环的次数 1 * n。如果包含多个嵌套的循环，则将继续计算倍数，例如 1 * n * m。
找到标记到的最大的值，就是运行时间的最大值，即算法复杂度描述的上界。

二、代码示例

1. 代码(1)

decimal Factorial(int n)
    {
      if (n == 0)
        return 1;
      else
        return n * Factorial(n - 1);
    }

阶乘（factorial），给定规模 n，算法基本步骤执行的数量为 n，所以算法复杂度为 O(n)。

2. 代码(2)

int FindMaxElement(int[] array)
    {
      int max = array[0];
      for (int i = 0; i < array.Length; i++)
      {
        if (array[i] > max)
        {
          max = array[i];
        }
      }
      return max;
    }

这里，n 为数组 array 的大小，则最坏情况下需要比较 n 次以得到最大值，所以算法复杂度为 O(n)。

3. 代码(3)

long FindInversions(int[] array)
    {
      long inversions = 0;
      for (int i = 0; i < array.Length; i++)
        for (int j = i + 1; j < array.Length; j++)
          if (array[i] > array[j])
            inversions++;
      return inversions;
    }

这里，n 为数组 array 的大小，则基本步骤的执行数量约为 n*(n-1)/2，所以算法复杂度为 O(n2)。

4.代码(4)

long SumMN(int n, int m)
    {
      long sum = 0;
      for (int x = 0; x < n; x++)
        for (int y = 0; y < m; y++)
          sum += x * y;
      return sum;
    }

给定规模 n 和 m，则基本步骤的执行数量为 n*m，所以算法复杂度为 O(n2)。

5.代码(5)

decimal Sum3(int n)
    {
      decimal sum = 0;
      for (int a = 0; a < n; a++)
        for (int b = 0; b < n; b++)
          for (int c = 0; c < n; c++)
            sum += a * b * c;
      return sum;
    }

这里，给定规模 n，则基本步骤的执行数量约为 n*n*n ，所以算法复杂度为 O(n3)。

6.代码(6)

decimal Calculation(int n)
    {
      decimal result = 0;
      for (int i = 0; i < (1 << n); i++)
        result += i;
      return result;
    }

这里，给定规模 n，则基本步骤的执行数量为 2n，所以算法复杂度为 O(2n)。

7.代码(7)

斐波那契数列：

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)

F() = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

int Fibonacci(int n)
    {
      if (n <= 1)
        return n;
      else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

这里，给定规模 n，计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

            fib(5)   
                 /             \     
           fib(4)                fib(3)   
         /      \                /     \
     fib(3)      fib(2)         fib(2)    fib(1)
    /     \        /    \       /    \

通过使用递归树的结构描述可知算法复杂度为 O(2n)。

8.代码(8)

int Fibonacci(int n)
    {
      if (n <= 1)
        return n;
      else
      {
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;

        for (int i = 2; i <= n; i++)
        {
          f[i] = f[i - 1] + f[i - 2];
        }

        return f[n];
      }
    }

同样是斐波那契数列，我们使用数组 f 来存储计算结果，这样算法复杂度优化为 O(n)。

9.代码(9)

int Fibonacci(int n)
    {
      if (n <= 1)
        return n;
      else
      {
        int iter1 = 0;
        int iter2 = 1;
        int f = 0;

        for (int i = 2; i <= n; i++)
        {
          f = iter1 + iter2;
          iter1 = iter2;
          iter2 = f;
        }

        return f;
      }
    }

同样是斐波那契数列，由于实际只有前两个计算结果有用，我们可以使用中间变量来存储，这样就不用创建数组以节省空间。同样算法复杂度优化为 O(n)。

10.代码(10)

通过使用矩阵乘方的算法来优化斐波那契数列算法。

#include <iostream>
using namespace std;

int fibonacci(int n) {
    int fib[n+1];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

int main() {
    int n = 10;
    cout << "Fibonacci number at position " << n << " is: " << fibonacci(n) << endl;
    return 0;
}

11.代码(11)

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的有序数据。算法适用于少量数据的排序，时间复杂度为 O(n2)。

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}