数据结构中的几种时间复杂度分析方式

简介: 数据结构中的几种时间复杂度分析方式


前言

时间复杂度,顾名思义,就是计算(说是预估可能更为准确)程序中运行所消耗的时间,数据结构中计算时间复杂度分别有以下方式:

  1. O
  2. Ω
  3. θ
  4. o

大O表示法(渐进上界(最坏情况))

定义:如果存在正常数c和n0使得当N ≥ \geq n0 时,T(N) ≤ \leq cf(N),则记为T(N) = O(f(N));

如图所示,当N大于等于某个常数之后,cf(N)某一部分可以看成T(N)的上界,cf(N)始终大于T(N)

大Ω表示法(渐进下界(最好情况))

定义:如果存在正常数c和n0使得当N ≥ \geq n0 时,T(N) ≥ \geq cg(N),则记为T(N) = Ω(g(N));

如图所示,当N大于等于某个常数之后,cg(N)某一部分可以看成T(N)的下界,cg(N)始终大于T(N)

假如T(N)代表某一个算法对于规模为N个输入数据所需要的处理时间,即处理N个数据所需要花费的时间为T(N),T(N)可能是非常复杂的,如上述两图,T(N)可能会存在上下波动的情况,显然不如f(N)与g(N)看着简洁,所以我们通常用f(N)与g(N)这样的更简单的函数来估计T(N)。

那么用f(N)与g(N)哪个函数来估计T(N)更好呢?假如boss要求你估计你算法的执行时间,如果回答cg(N),那么就太不谦虚了,且真正的执行时间T(N)还大于cg(N),如果用cg(N)来代表预估的执行时间,那么真正的执行时间T(N)永远达不到所预估的执行时间cg(N),直接被炒鱿鱼了。所以应该用真正的执行时间T(N)的上界,即cf(N)来代表预估的执行时间,这样才是准确的,因为这个情况下才能达到目标值,实际执行时间T(N)会比预估的执行时间cf(N)要少

所以我们预估算法的执行时间的时候,通常是取上界而不是下界(因为算法实际耗时可能要比下界多得多)

所以通常情况下预估算法执行时间和效率,我们会用大O表示法,即第一种方法,T(N)=O(f(N))

θ表示法(渐进上下界)

定义:T(N) = θ(h(N)),当且仅当T(N) = O(h(N))且T(N) = Ω(h(N));

这个的意思是,h(N)既是T(N)的上界又是T(N)的下界,即h(N)在某种情况下与T(N)重合了。

我们发现,在这种情况下,用h(N)来估计T(N)会更准确。我们称T(N)=θ(h(N))为θ表示法。

θ表示法比大O表示法更准确,因为大O表示法仅提供了上界,而θ表示法既提供了上界也提供了下界。

但是为什么平时一般用大O表示法而不用θ表示法呢?因为θ表示法的函数很难找,这一函数几乎和T(N)重合了。(θ读西塔)

小o表示法

定义:如果T(N) = O(p(N))且T(N) ≠ \neq= θ(p(N)),则T(N) = o(p(N))

在N大于等于某个常数的时候,cp(N)是完全大于T(N)的,不存在等于的情况,这种表示法实际上就是把大O表示法的等号去掉了,我们称之为小o表示法。

由此我们可以看出大O表示法的缺点:大O表示法估计出一个上界,但是这个上界不一定是最小上界,没必要紧贴着T(N)。从某种意义上来说,我们用大O表示法估计T(N)的时候,有时候可能会和小o表示法重合,即大O表示法包含小o表示法

如下示例:

T(N) = N 2 N^2N2            f(N) = N 3 N^3N3            T(N) = O(f(N))

f(N)满足大O表示法对T(N)的估计,所以T(N)=O(f(N))完全没问题,只要T(N)小于等于f(N)即可。而小于等于也包括小于的情况,显然大O表示法这样表示是不好的,因为这样表示太谦虚了。因此在实际应用中,我们用大O表示法估计的时候,尽量找最小的上界。而在考研中,我们尽量用θ表示法来估计T(N),这样更准确些

时间复杂度分析的最坏、最好与平均情况

  1. 最坏情况指T(N)耗时最大情况,即用大O表示法(考研如果不指定,一般都用这种方法)
  2. 最好情况指T(N)耗时最小情况,即用大Ω表示法
  3. 平均情况指T(N)耗时平均情况,即用θ表示法
目录
相关文章
|
4月前
|
算法 搜索推荐 程序员
数据结构中时间复杂度的介绍
冒泡排序是通过重复遍历数组,比较并交换相邻元素来排序数组的。因为它包含两层嵌套循环,每层循环的最大迭代次数近似于n,所以时间复杂度是O(n²)。 通过上述分析,我们可以看到不同代码结构对算法性能有着显著的影响。在设计数据结构和算法时,理解并计算时间复杂度是非常重要的,它帮助程序员选择或优化算法,以处理更大的数据集或提高程序的运行速度。
25 2
|
2月前
|
存储 算法
【数据结构】——时间复杂度与空间复杂度
【数据结构】——时间复杂度与空间复杂度
|
4月前
|
存储 测试技术
【数据结构】手把手分析:链式二叉树的实现
【数据结构】手把手分析:链式二叉树的实现
31 5
|
4月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
4月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
4月前
|
算法
数据结构和算法学习记录——时间复杂度、空间复杂度相关练习题
数据结构和算法学习记录——时间复杂度、空间复杂度相关练习题
31 2
|
4月前
|
算法
数据结构和算法——散列函数的构造方法(直接定址法、除留余数法、数字分析法、折叠法、平方取中法、ASCII码加和法、前三字符移位法)
数据结构和算法——散列函数的构造方法(直接定址法、除留余数法、数字分析法、折叠法、平方取中法、ASCII码加和法、前三字符移位法)
40 0
|
4月前
|
算法 搜索推荐
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
29 0
|
4月前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
30 0
|
4月前
|
算法 Shell C语言
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)
41 0