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

>>算法中重复执行次数和算法的执行时间成正比的语句对算法运行时间的贡献最大

>>n越大算法的执行时间越长

排序：n为记录数

矩阵：n为矩阵的阶数

多项式：n为多项式的项数

集合：n为元素个数

树：n为树的结点个数

图：n为图的顶点数或边数

2.数学符号“O”的定义为：

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n) = O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤Cf(n)。

表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。

语句的频度（Frequency Count )

重复执行的次数：n*n; T( n ) = O ( n ^2) 即：矩阵加法的运算量和问题的规模n的平方是同一个量级


n * n阶矩阵加法： 
for( i = 0; i < n; i++)     
    for( j = 0; j < n; j++)
         c[i][j] = a[i][j] + b[i][j];

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

>>找出语句频度最大的那条语句作为基本语句

>>计算基本语句的频度得到问题规模n的某个函数f(n)

>>取其数量级用符号“O”表示

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

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊

时间复杂度T(n)按数量级递增顺序为：

各种数量级的时间复杂度：

常用时间复杂度频率表：

渐进空间复杂度

1.空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n))

>>其中n为问题的规模(或大小)

2.算法要占据的空间

>>算法本身要占据的空间，输入/输出，指令，常数，变量等

>>算法要使用的辅助空间

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/496418