算法和算法分析时间复杂度和空间复杂度的分析

Myth丶恋晨 2023-10-14 18:00 70阅读 0赞

#### 文章目录 ####

*  算法与程序
 *   *  \*\*程序=数据结构+算法\*\*
     *  算法和算法分析
     *   *  算法特性
         *   *  有穷性
             *  确定性
             *  可行性
             *  输入
             *  输出
         *  算法设计的要求
         *  算法时间效率的度量
     *  时间复杂度
     *   *  定理1.1
         *  分析算法时间复杂度的基本方法
         *  复杂算法的处理
     *  空间复杂度

## 算法与程序 ##

*  **算法**是解决问题的一种方法或一个过程,考虑如何将输入转化成输出,一个问题可以有多个算法
 *  **程序**是用某种程序设计语言对算法的具体实现

### **程序=数据结构+算法** ###

*  数据结构通过算法实现操作
 *  算法根据数据结构设计程序

### 算法和算法分析 ###

#### 算法特性 ####

**一个算法必须具备以下五个重要特征**

##### 有穷性 #####

**一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成**

##### 确定性 #####

**算法的每一条指令必须有确切的含义,没有二义性,在任何条件下,只有唯一的一条执行路径,即对于相同的输入只能得到相同的输出**

##### 可行性 #####

**算法是可执行的,算法描述的操作可以通过已经实现的基本操作执行有限次来实现**

##### 输入 #####

**一个算法有零个或多个输入**

##### 输出 #####

**一个算法有一个或多个输出**

#### 算法设计的要求 ####

*  正确性(Correctness)
    
     *  不含语法错误
     *  能得到满足要求的结果
     *  对于精心选择的,典型,苛刻且带有刁难性的输入能得到满足要求的结果
     *  一切合法的输入数据都能得出满足要求的结果
 *  可读性(Readability)
    
     *  首先为了人的阅读和交流,其次才是计算机执行
     *  晦涩难读的算法容易调试
 *  健壮性(Robustness)
    
     *  输入**非法数据**时算法做出相应的处理,而不是出错
     *  处理错误方法,不应该中断程序执行,而是返回一个表示错误或错误性质的值,以便在更高的抽象层次上处理
 *  高效性(Efficiency)
    
     *  要求花费尽量少的时间和尽量低的存储要求

**当算法满足前三的要求时,主要考虑算法的效率,通过算法的效率高低来评判不同算法的优劣程度**

**算法效率以以下两个方面来考虑**

1.  时间效率:指的是算法所耗费的时间
2.  空间效率:指的是算法执行过程中耗费的存储空间

*  **时间效率和空间效率有时候是矛盾的**

#### 算法时间效率的度量 ####

*  **使用在计算机上执行所消耗的时间来度量**
 *  两种度量方法
    
     *  事后统计
        
         *  将算法实现,测算其时间和空间开销
         *  缺点:花费时间和精力,结果依赖于计算机的软硬件等环境因素
     *  事前分析(推荐使用这个)
        
         *  对算法所消耗资源的一种估算方法
        
        **(事前分析)算法运行时间=一个简单操作所需要的时间\*简单操作次数**
        
        \**(事前分析)算法运行时间=∑每条语句的执行次数(又称语句频度)该语句执行一次所需要的时间*
        
        **注意:每条语句执行所需时间由计算机软硬件条件影响的,与算法无关**
        
        **所以,我们可以假设执行每条语句所需的时间均为单位时间**

例如

for(i=1;i<=n;i++){
        								//n+1次
    	for(j=1;j<=n;j++){
        							//n*(n+1)次
    		c[i][j]=0;								//n*n次
    		for(k=0;k<n;k++){
        						//n*n*(n+1)次
    			c[i][j]=c[i][j]+a[i][k]*b[k][j];	//n*n*n次
    		}
    	}
    }

我们把算法所消耗的时间定义为**该算法中每条语句的频度之和**则上述算法的时间消耗T(n)为

**T(n)=2n^3 + 3n^2 + 2n+1**一个关于n的函数

*  **为了方便比较不同算法时间效率,我们仅比较它们的数量级**

例如:两个不同的算法,时间消耗分别是

**T(n)=10n^2 与 T(n)=5n^3;**

### 时间复杂度 ###

*  若有某个辅助函数f(n),使得当n趋近于无穷大是,T(n)/f(n)的极限值为**不等于零的常数**,则称为f(n)是T(n)的同数量级函数,记作T(n)=O(f(n)),称O(f(n))为**算法的渐进时间复杂度**(*O是数量级的符号*),简称**时间复杂度**

**T(n)=2n^3 + 3n^2+2n+1**

**其中当n->∞时,T(n)/n3->2,这表示n充分大时,T(n)与n3是同阶或同数量级,引入"O"记号,则T(n)可以记作**

**T(n)=O(n^3)**

**这就是求矩阵相城问题的算法的渐进时间复杂度**

一般情况下,不必计算所有操作的执行次数,而只考虑算法中**基本操作**执行的次 数, 它是问题规模n的某个函数,用T(n)表示

**算法中基本语句重复执行次数是问题规模n的某个函数f(n),算法的时间量度记作:T(n) = O(f(n)**

**它表示随着n的增大,算法执行的时间的增长率和f(n)的增长率相同,称为渐进时间复杂度**

**算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))**

*  基本语句.
    
     *  算法中重复执行次数和算法的执行时间成正比的语句
     *  对算法运行时间的贡献最大
     *  执行次数最多
 *  问题规模n
    
    n越大算法执行时间越长
    
     *  排序:n为记录数
     *  矩阵:n为矩阵的阶数
     *  多项式:n为多项式的项数
     *  集合:n为元素个数
     *  树:n为树的结点个数
     *  图:n为图的顶点数或边数

#### 定理1.1 ####

若f(n)=a\_n\*n ^ m +a\_(n-1)\*n(m-1)+…+a\_1\*n+a\_0是m次多项式,则\*\*T(n)=O(nm).\*\*

#### 分析算法时间复杂度的基本方法 ####

1.  找出语句频度最大的那条语句作为基本语句
2.  计算基本语句的频度得到问题规模n的某个函数f(n)
3.  取其数量级用符号"**O**"表示

eg
    x=0;y=0;
    for(int k=0;k<n;k++){
        	//n+1
        x++;				//n
    }
    for(int i=0;i<n;i++){
        	//n+1
    	for(int j=0;j<n;j++){
        //n*(n+1) 频度最大
            y++;			//n*n
        }        
    }

*f(n)=n(n+1) T(n)=O(n^2)*\*

**时间复杂度是由嵌套最深层语句的频度决定的**

**算法中的基本操作语句为 第五行**

![在这里插入图片描述][47949dcd426c4fd2bbdf653f6fe6721e.png_pic_center]

for(i=1;i<=n;i++){
        
        for(j=1;j<=i;j++){
        
            for(k=1;k<=j;k++){
        
                x=x+1;
            }
        }
    }

![在这里插入图片描述][189242df63d042fba71ad47dea81e6e4.png_pic_center]

i=1;
    while(i<=n)
    	i=i*2;

![在这里插入图片描述][7eaf7156a837413ba373cdb19bdf113c.png_pic_center]

![在这里插入图片描述][33de774c28024b10937d13c46c5c2822.png_pic_center]

**请注意:有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同**

例如
    	for(i=0;i<n;i++)
    		if(a[i]==e)return i+1;//找到,返回第几个元素
    	return 0;
    最好情况 : 1次;
    最坏情况 : n次;
    平均时间复杂度为:O(n)

*  最坏时间复杂度:指在最坏情况下,算法的时间复杂度.
 *  平均时间复杂度:指在所有可能输入实例在等概率出现的情况下,算法的期望运行时间
 *  最好时间复杂度:指在最好情况下,算法的时间复杂度
    
     *  **一般总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长**

#### 复杂算法的处理 ####

*  对于复杂算法,可以分成容易估算的部分,然后利用大O加法法则和乘法法则,计算算法的时间复杂度:
    
    a)加法规则
    
    **T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))**
    
    b)乘法规则
    
    \**T(n)=T1(n)T2(n)=* \**O(f(n))O(g(n))=* \**O(f(n)g(n))*

### 空间复杂度 ###

*  **空间复杂度: 算法所需存储空间的度量**
    
    **记作: S(n)=O(f(n))**
    
    **其中n为问题的规模(或大小)**
    
     *  **算法要占据的空间**
        
         *  算法本身要占据空间,输入/输出,指令,常数,变量等
         *  算法要使用的**辅助空间**

算法1
    	for(i=0;i<n/2;i++){
        
    		t=a[i];//调用了一个空间
    		a[i]=a[n-i-1];
    		a[n-i-1]=t;
    	}
    //S(n)=O(1);	
    
    算法2
    	for(i=0;i<n;i++){
        
    		b[i]=a[n-i-1];//调用了n个空间
    	}
    	for(i=0;i<n;i++){
        
    		a[i]=b[i];
    	}
    //S(n)=O(n)

常数,变量等  
\- 算法要使用的**辅助空间**

**抽象数据类型 = 数据的逻辑结构 + 抽象运算 (运算的功能描述)**

[47949dcd426c4fd2bbdf653f6fe6721e.png_pic_center]: https://img-blog.csdnimg.cn/47949dcd426c4fd2bbdf653f6fe6721e.png#pic_center
[189242df63d042fba71ad47dea81e6e4.png_pic_center]: https://img-blog.csdnimg.cn/189242df63d042fba71ad47dea81e6e4.png#pic_center
[7eaf7156a837413ba373cdb19bdf113c.png_pic_center]: https://img-blog.csdnimg.cn/7eaf7156a837413ba373cdb19bdf113c.png#pic_center
[33de774c28024b10937d13c46c5c2822.png_pic_center]: https://img-blog.csdnimg.cn/33de774c28024b10937d13c46c5c2822.png#pic_center