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

81 阅读 0 评论 54 点赞

我是靠谱客的博主单纯裙子，这篇文章主要介绍查缺补漏（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）内容请搜索靠谱客的其他文章。

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