查缺补漏（3） - 算法复杂度

100 阅读 0 评论 66 点赞

我是靠谱客的博主单纯裙子，最近开发中收集的这篇文章主要介绍查缺补漏（3） - 算法复杂度，觉得挺不错的，现在分享给大家，希望可以做个参考。

问题1：关于算法复杂度

KhanAcademy

衡量算法复杂度，一般是指算法花费的时间长短，这取决于input的size和随着input size增长而算法时间增长的速度:

1) The size of its input;

2) The rate of growth: how fast a function grows with the input size.

1. 算法复杂度的标记:

$Theta: $ an asympototic tight bound.类似于上确界的定义

$O:$ an asympototic upper bound.类似于上界的定义

$Omega:$ an asympototic lower bound.类似于下界的定义

If f(n) is O(g(n)) this means that f(n) grows asymptotically no faster than g(n)

If f(n) is Θ(g(n)) this means that f(n) grows asymptotically at the same rate as g(n)

$Theta(g(n))$表示当n足够大时，算法在最坏的情况下，存在某常数$k_1,k_2$，使得执行时间会在$k_1cdot g(n)$和$k_2cdot g(n)$之间。

2. 算法复杂度的大小比较:

constant < logarithmic < linear < polynomial < exponential < factorial

代入具体的数字，有

$Theta(1) < Theta(lg n) < Theta(nlg n) < Theta(n^2) < Theta(2^n) < Theta(n!)$

并且$Theta(n^b) < Theta(a^n), forall a > 1, b geq 1$,$Theta(n!) > Theta(a^n), forall a>1$

转载于:https://www.cnblogs.com/RRRRecord/p/7860092.html

以上就是单纯裙子为你收集整理的查缺补漏（3） - 算法复杂度的全部内容，希望文章能够帮你解决查缺补漏（3） - 算法复杂度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。