数据结构基础算法复杂度分析（二）典例篇

迈不过友情╰ 2022-08-03 05:28 173阅读 0赞

**示例代码（1）**

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

【分析】  
阶乘（factorial），给定规模 n，算法基本步骤执行的数量为 n，所以算法复杂度为 O(n)。  
  
**示例代码（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）**

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）**

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(n^2)。  
  
**示例代码（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(n^3)。  
  
**示例代码（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）**  
斐波那契数列：  
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(2^n)。   
   
**示例代码（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）**

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）**

static int Fibonacci(int n)
        {
          if (n <= 1)
            return n;
    
          int[,] f = { { 1, 1 }, { 1, 0 } };
          Power(f, n - 1);
    
          return f[0, 0];
        }
    
        static void Power(int[,] f, int n)
        {
          if (n <= 1)
            return;
    
          int[,] m = { { 1, 1 }, { 1, 0 } };
    
          Power(f, n / 2);
          Multiply(f, f);
    
          if (n % 2 != 0)
            Multiply(f, m);
        }
    
        static void Multiply(int[,] f, int[,] m)
        {
          int x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0];
          int y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1];
          int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0];
          int w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1];
    
          f[0, 0] = x;
          f[0, 1] = y;
          f[1, 0] = z;
          f[1, 1] = w;
        }

【分析】

通过使用矩阵乘方的算法来优化斐波那契数列算法。优化之后算法复杂度为O(log2(n))。  
  
**示例代码（11）**  
更简洁的代码如下。

static double Fibonacci(int n)
        {
          double sqrt5 = Math.Sqrt(5);
          double phi = (1 + sqrt5) / 2.0;
          double fn = (Math.Pow(phi, n) - Math.Pow(1 - phi, n)) / sqrt5;
          return fn;
        }

**示例代码（12）**

private static void InsertionSortInPlace(int[] unsorted)
        {
          for (int i = 1; i < unsorted.Length; i++)
          {
            if (unsorted[i - 1] > unsorted[i])
            {
              int key = unsorted[i];
              int j = i;
              while (j > 0 && unsorted[j - 1] > key)
              {
                unsorted[j] = unsorted[j - 1];
                j--;
              }
              unsorted[j] = key;
            }
          }
        }

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