算法的基础知识-时间复杂度

爱被打了一巴掌 2023-10-04 16:27 42阅读 0赞

#### 算法基础知识 ####

1.  #### 算法定义 ####
    
    算法（Algorithm）这个单词最早出现在波斯数学家阿勒花刺子密在公元825年所写的《印度数学算术》中。如今普遍认可的对算法的定义是：
    
    **算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作**
2.  #### 算法的特性 ####
    
     *  输入输出
        
        这个比较容易理解，算法具有零个或者多个输入
     *  有穷性
        
        有穷性是指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
     *  确定性
        
        算法的每一步骤都具有确定的含义，不会出现二义性。
     *  可行性
        
        算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
3.  #### 算法设计的要求 ####
    
     *  正确性
        
        算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
        
        但是算法的“正确”通常在用法上有很大的差别，大体分为以下四个层次。
        
        1.  算法程序没有语法错误
        2.  算法程序对于合法的输入数据能够产生满足要求的输出结果
        3.  算法程序对于非法的输入数据能够得出满足规格说明的结果
        4.  算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
     *  可读性
        
        算法设计的另一目的是为了便于阅读、理解和交流
     *  健壮性
        
        当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
     *  时间效果高和存储量低
        
        设计算法应该尽量满足时间效率高和存储量低的需求
4.  #### 算法效率的度量方法 ####
    
     *  事后统计方法
        
        这种方法主要时通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
     *  事前分析估算方法
        
        在计算机程序编制前，依据统计方法对算法进行估算
        
        一个程序的运行时间，依赖于算法的好坏和问题的输入规模。
        
        最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤
5.  #### 函数的渐近增长 ####
    
    函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,f(n)总比g(n)大，那么，我们说f(n)的增长渐近快于g(n)
    
    判断一个算法的效率时，函数中的常数和其他次要项常常忽略，而更应该关注主项(最高级项)的阶数
    
    某个算法，随着n的增大，它会越来越优越于另一个算法，或者越来越差于另一算法
6.  #### 算法时间复杂度 ####
    
     *  算法时间复杂度定义
        
        在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数
     *  推导大O阶方法
        
        **推导大O阶方法：**
        
        **1.用常数1取代运行时间中的所有加法常数**
        
        **2.在修改后的运行次数函数中，只保留最高级阶项**
        
        **3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶**
     *  常数阶
        
        执行一次的就是常数阶，比如：
        
            int sum = 0,n = 100
            sum = (1 + n) * n / 2
            printf("%d",sum)
        
        这个算法的时间复杂度为O(1)
        
        即便这个语句有100行，因为都是常数项，O(4),O(10),O(100)等其他数字，也都是O(1)
     *  线性阶
        
        线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特性语句或者某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况
        
        下面这段代码，它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次
        
            int i;
            for(i = 0,i < n,i++){
                    
            	/*时间复杂度为O(1)的程序步骤序列*/
            }
     *  对数阶
        
        下面这段代码
        
            int count = 1
            while(count < n){
                    
            	count = count * 2
            }
        
        由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2^x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)
     *  平方阶
        
        下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)
        
            int i,j
            for(i = 0;i < n;i++){
                    
            	for(j = 0;j < n;j++){
                    
            		/*时间复杂度为O(1)的程序步骤序列*/
            	}
            }
        
        而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n^2)
        
        如果外循环的循环次数改为了m，时间复杂度就变为了O(m\*n)
        
            int i,j
            for(i = 0;i < m;i++){
                    
            	for(j = 0;j < n;j++){
                    
            		/*时间复杂度为O(1)的程序步骤序列*/
            	}
            }
        
        所以我们得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数
        
        再看一个循环嵌套
        
            int i,j;
            for(i = 0;i < n;i++){
                    
            	for(j = i;j < n;j++){
                    /*注意int j = i而不是0*/
            		/*时间复杂度为O(1)的程序*/
            	}
            }
        
        由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次，当i=n-1时，执行了1次。所以总次数：
        
        n+(n-1)+(n-2)+…+1=n(n+1)/2
        
        用推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留n2/2;第三条，去除这个项相乘的常数，也就是去除1/2，最终这段代码的时间复杂度为O(n2)
        
        继续看一些例子：
        
            int i,j;
            for(i = 0;i < n;i++){
                    
            	function(i);
            }
        
        上面的代码调用了一个函数function
        
            void function(int count){
                    
            	print(count)
            }
        
        函数体就是打印这个参数。其实很好理解，function的时间复杂度时O(1)。所以整体的时间复杂度就是O(n)
        
        假如function是这样的
        
            void function(int count){
                    
            	int j;
            	for(j = count;j < n;j++){
                    
            		/*时间复杂度为O(1)的程序步骤序列*/
            	}
            }
        
        事实上，这和刚才的例子是一样的，最终的时间复杂度为O(n^2)
        
            n++;		/*执行次数为1*/
            function(n);		/*执行次数为n*/
            int i,j;			
            for(i = 0;i < n;i++){
                    	/*执行次数为n^2*/
            	function(i)
            }
            for(i = 0;i < n;i++){
                    		/*执行次数为n(n+1)/2*/
            	for(j = i;j < n;j++){
                    
            		/*时间复杂度为O(1)的程序步骤序列*/
            	}
            }
        
        它的执行次数f(n)=1 + n + n^2 + n(n+1)/2 + 3n^2/2 + 3n/2 + 1,根据推导大O阶的方法，最中这段代码的时间复杂度为O(n^2)
7.  #### 常见的时间复杂度 ####
    
    <table> 
     <thead> 
      <tr> 
       <th>执行次数函数</th> 
       <th>阶</th> 
       <th>非正式术语</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>12</td> 
       <td>O(1)</td> 
       <td>常数阶</td> 
      </tr> 
      <tr> 
       <td>2n+3</td> 
       <td>O(n)</td> 
       <td>线性阶</td> 
      </tr> 
      <tr> 
       <td>3n^2+2n+1</td> 
       <td>O(n^2)</td> 
       <td>平方阶</td> 
      </tr> 
      <tr> 
       <td>5log2n+20</td> 
       <td>O(logn)</td> 
       <td>对数阶</td> 
      </tr> 
      <tr> 
       <td>2n+3nlog2n+19</td> 
       <td>O(nlogn)</td> 
       <td>nlog2n阶</td> 
      </tr> 
      <tr> 
       <td>6n<sup>3+2n</sup>2+3n+4</td> 
       <td>O(n^3)</td> 
       <td>立方阶</td> 
      </tr> 
      <tr> 
       <td>2^n</td> 
       <td>O(2^n)</td> 
       <td>指数阶</td> 
      </tr> 
     </tbody> 
    </table>
    
    常用的时间复杂度所耗费的时间从小到大依次是
    
        O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
8.  #### 最坏情况和平均情况 ####
    
    最坏情乱运行时间是一种保证，那就是运行时间将不会再坏了。再应用中，这是一种重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间
    
    对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般没有特殊说明的情况下，都是指最坏时间复杂度
9.  #### 算法空间复杂度 ####
    
    空间复杂度就是所占的存储空间，算法空间复杂度的公式：S(n)=O(f(n)),其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数
    
    一般情况下，一个程序再机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需要的辅助单元即可。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)
    
    通常，我们都使用时间复杂度来指运行时间需求，使用空间复杂度指空间需求。当不用限定词地使用复杂度时，通常都是指时间复杂度。