算法分析（时间复杂度和空间复杂度）

梦里梦外; 2022-04-22 14:24 275阅读 0赞

算法分析（时间复杂度和空间复杂度）  
对于一个给定的算法需要做两项分析，第一就是证明算法的正确性，第二就是计算算法的复杂度。算法的复杂度包括时间复杂度和空间复杂度。

1  度量算法效率的方法  
共存在两种方法：事后统计法和事前分析估计算法。

事后统计法：先将算法实现，然后输入适当的数据运行，计算算法的时间复杂度和空间复杂度。

事前分析估算法（渐进复杂度）：对算法所消耗资源的一种估算方法。比较常用。

本文主要是渐进复杂度的解释。

2  算法的时间复杂度  
影响算法时间复杂度的主要因素是问题规模。

问题规模：是指输入量的多少。规模大的输入量需要的运行时间更长。所以运行算法所需要的时间T的问题是问题规模n的函数，记作T(n)。

为了客观的表示一个算法的运行时间，可以用基本语句的执行次数来度量算法的工作量。

定义：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

通常采用大O记号表示。

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

3  求解时间复杂度的步骤  
（1）找出算法的基本语句，一般是循环体。

（2）计算基本语句执行次数的数量级，也就是基本语句执行次数函数的最高次幂。可忽略低次幂和系数。

（3）用大O记号表示时间复杂度。

4  计算时间复杂度常用性质  
（1）一些简单的输入输出赋值语句，近似为O(1)。

（2）对于顺序结构需要求和法则。

求和法则：若T1(n)=O(f(n))、 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))。

（3）对于选择结构（if判断），需要看执行语句。

（4）对于循环结构采用乘法法则。

乘法法则：若T1(n)=O(f(n))、 T2(n)=O(g(n)),则 T1\*T2=O(f(n)\*g(n))。

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。

5  常用时间复杂度示例  
常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3)。由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)＜Ο(n!)。

（1）Ο(log2n)（二分查表）

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

（2）O(n)（一次for循环）

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

（3）Ο(nlog2n)（快排）

void quickSort(int arr[], int left, int right)  
    {  
        if (left < right)  
        {  
            int key = arr[left];    
            int i = left, j = right;  
            while (i < j)  
            {  
                while (arr[j] > key && j > i) 
                    j--;  
                if (i < j)     
                    arr[i++] = arr[j];  
                while (arr[i] < key && i < j)  
                    i++;  
                if (i < j)  
                    arr[j--] = arr[i];  
            }  
            arr[i] = key;  
            quickSort(arr, left, i - 1);  
            quickSort(arr, i + 1, right);  
        }  
    }

（4）O(n2)（冒泡排序）

void BubbleSort(int arr[],int num)
    {
        int i,j;
        int temp=0;
        for(i=0;i<num-1;i++)
        {
            for(j=0;j<num-i-1;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

6  算法的空间复杂度

空间复杂度定义了为算法所消耗的存储空间。是算法运行是所占用存储空间大小的量度。