入门讲解：李春葆《数据结构教程》01章 - 从头开始：算法简介与时间复杂度分析(第二部分) - 4.2

• 一个算法是由控制结构（顺序、分支和循环三种）和原操作构成的。

1. 顺序结构：按照所述顺序处理
   分支结构：根据判断条件改变执行流程
   循环结构：当条件成立时，反复执行给定的处理操作
2. 指固有数据类型的操作，如+、-、*、/、++和–等

• 算法执行时间取决于两者的综合效果。

4.2.1 算法分析方式

• 事后分析统计方法：编写算法对应程序，统计其执行时间。
  编写程序的语言不同，执行程序的环境不同以及其它因素造成不能用绝对执行时间进行比较。
  
• ???? 事前估算分析方法：撇开上述因素，认为算法的执行时间是问题规模n的函数。
  

4.2.2 分析算法的执行时间

• 求出算法所有原操作的执行次数（也称为频度），它是问题规模n的函数，用T(n)表示。
• 算法执行时间大致 = 原操作所需的时间×T(n)。所以T(n)与算法的执行时间成正比。为此用T(n)表示算法的执行时间。
• 比较不同算法的T(n)大小得出算法执行时间的好坏。

4.2.3 算法的执行时间用时间复杂度来表示

算法中执行时间T(n)是问题规模n的某个函数f(n)，记作：T(n) = O(f(n))

记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同 --> 趋势分析

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。

本质上讲，是一种T(n)最高数量级的比较。

例如：T(n) = 2n 2 n^2n2+2n+1 = O(n 2 n^2n2)

???? 一般地：

• 一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。
• 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。
• 其余常用的算法时间复杂度还有平方阶O(n 2 n^2n2)、立方阶O(n 3 n^3n3)、对数阶O(l o g 2 n log_2nlog2n)、指数阶O(2 n 2^n2n)等。

各种不同算法时间复杂度的比较关系如下：

算法时间性能比较：假如求同一问题有两个算法：A和B，如果算法A的平均时间复杂度为O(n)，而算法B的平均时间复杂度为O(n 2 n^2n2)。一般情况下，认为算法A的时间性能好比算法B。

某算法的时间复杂度为O(n 2 n^2n2)，表明该算法的执行时间与n 2 n^2n2成正比。

4.2.4 简化的算法时间复杂度分析

算法中的基本操作一般是最深层循环内的原操作

在算法分析时，计算T(n)时仅仅考虑基本操作的运算次数

算法执行时间大致 = 基本操作所需的时间×其运算次数

4.2.5 最好、最坏和平均时间复杂度分析

4.2.6 算法空间复杂度分析

空间复杂度：用于量度一个算法运行过程中临时占用的存储空间大小(算法中需要的辅助变量所占用存储空间的大小)。一般也作为问题规模n的函数，采用数量级形式描述，记作：S(n) = O(g(n))

若一个算法的空间复杂度为O(1)，则称此算法为原地工作或就地工作算法。该算法执行所需辅助空间大小与问题规模n无关。

❓ 为什么空间复杂度分析只考虑临时占用的存储空间

⭐️ 分析如下算法的空间复杂度

// 临时占用的存储空间：函数体内分配的空间
int fun(int n){  
 int i，j，k，s;
 s=0;
 for (i=0;i<=n;i++)
     for(j=0;j<=i;j++)
         for (k=0;k<=j;k++)
             s++; 
 return(s)
}

???? 算法中临时分配的变量个数与问题规模n无关，所以空间复杂度均为O(1)

5.数据结构+算法=程序