数据结构--时间复杂度的计算.doc
版权申诉
78 浏览量
2022-07-11
11:38:50
上传
评论
收藏 36KB DOC 举报
数据结构--时间复杂度的计算
时间复杂度计算
首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某
个算法的时间耗费，它是该算法所求解问题规模 n 的函数，而后者是指当问题规
模趋向无穷大时，该算法时间复杂度的数量级。
当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，
在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度 T(n)=O(f(n))
简称为时间复杂度，其中的 f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相
关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不
会比它更长。
常见的时间复杂度，按数量级递增排列依次为：常数阶 O(1)、对数阶 O(log2n)、
线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n^2)、立方阶 O(n^3)、k 次方
阶 O(n^k)、指数阶 O(2^n)。
定义：如果一个问题的规模是 n，解这一问题的某一算法所需要的时间为 T(n)，它是 n 的某
一函数 T(n)称为这一算法的“时间复杂性”。
当输入量 n 逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。
我们常用大 O 表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大 O 表示只是说
有上界，由定义如果 f(n)=O(n)，那显然成立 f(n)=O(n^2)，它给你一个上界，但并不是上确界，
但人们在表示的时候一般都习惯表示前者。
此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，
那就称这样的算法是最佳算法。
“大 O 记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间
表达为 n 的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它
需要“通过 logn 量级的步骤去检索一个规模为 n 的数组”记法 O ( f(n) )表示当 n 增大时，运行
时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差
异。例如，一个低附加代价的 O(n2)算法在 n 较小的情况下可能比一个高附加代价的 O(nlogn)
算法运行得更快。当然，随着 n 足够大以后，具有较慢上升函数的算法必然工作得更快。
O(1)
Temp=i;i=j;j=temp;
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模 n 无关的常数。算法
评论0
最新资源