时间复杂度总结
2021/9/25 6:41:12
本文主要是介绍时间复杂度总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
描述时间复杂度的渐进记号
Θ
定义:
\[f(n)=\Theta(g(n))\\ \exist c_1,c_2,n_0,使得:\forall n\geq n_0,有 0\leq c_1g(n)\leq f(n)\leq c_2g(n) \]即存在常数c1,c2,使得在n足够大(n>n0)的时候,f(n)能被夹在c1g(n),c2g(n)中间,称g(n)是f(n)的渐进紧确界。Θ符号确定了一个函数的渐进上界和下界,即时间复杂度定为g(n)的常数倍。
O
定义:
\[f(n)=O(g(n))\\ \exist c,n_0,使得:\forall n\geq n_0,有 0\leq f(n)\leq cg(n) \]即存在常数c,使得在n足够大(n>n0)的时候,f(n)的上界是cg(n)。O符号确定了一个函数的渐进上界,这个上界可能是渐进紧确的,也可能不是,即最坏情况下复杂度为c*g(n),但是不一定取到最坏情况。通常都采用O符号表示算法的时间复杂度。
o
定义:
\[f(n)=o(g(n))\\ \forall c,\quad \exist n_0,使得:\forall n\geq n_0,有 0\leq f(n)< cg(n) \]即存对于任意常数c,均有在n足够大(n>n0)的时候,f(n)会小于cg(n)。o符号确定了一个函数的渐进上界,这个上界不是渐进紧确的,即复杂度一定不超过g(n),即使在最坏情况下也达不到g(n)的程度。
Ω,ω
与O,o类似,Ω,ω分别定义了f(n)的渐进下界和渐进非紧确下界,不过使用比较少,不多论述。
时间复杂度的计算
循环为主的算法,一般直接计算循环次数即可。
而对于递归算法,要写出递归式,然后求解,令T(n)表示规模为n的数据的运行时间。大致可以分成两种情况
- T(n)=T(n-a)+f(n)。即每次递归将问题规模缩小一个常数。这种情况一般直接将公式整体展开求级数和即可,即使不能求精确解也能利用放缩估计上界。不过并不是所有类似的递归式都能如此求解(如暴力递归计算斐波那契数列的算法的时间复杂度)。
- T(n)=aT(n/b)+f(n)。即每次递归将问题规模缩小常数倍,并分解成若干个缩小规模的子问题,每次需要f(n)的时间求解,合并,分解。这种情况一般用主定理求解
主定理(简化版本):
\[令f(n)=\Theta(n^d)\\ if \quad d>log_b(a),\quad T(n)=O(n^d)\\ if \quad d=log_b(a),\quad T(n)=O(n^d*log(n))\\ if \quad d<log_b(a),\quad T(n)=O(n^{log_b(a)}) \]这篇关于时间复杂度总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)