渐近分析

算法的渐近分析是指定义其运行时性能的数学边界/框架。通过渐近分析，我们可以很好地得出算法的最佳情况、平均情况和最坏情况。

渐近分析是有输入界限的，即如果算法没有输入，则可以断定它在恒定时间内工作。除了"输入"之外，所有其他因素都被认为是恒定的。

渐近分析是指以数学计算单位计算任何操作的运行时间。例如，一个操作的运行时间被计算为 f(n) 并且可能对于另一个操作它被计算为 g(n ²）。这意味着第一个操作的运行时间会随着 n的增加而线性增加，而第二个操作的运行时间会随着 n的增加而呈指数增长。同样，如果 n 非常小，则两个操作的运行时间几乎相同。

通常，算法所需的时间分为三种类型-

Best Case-程序执行所需的最短时间。 Average Case-程序执行所需的平均时间。 Worst Case-程序执行所需的最长时间。

渐近符号

以下是常用的渐近符号来计算算法的运行时间复杂度。

Ο 符号 Ω 符号 θ 符号

O符号，Ο

符号Ο(n)是表达算法运行时间上限的正式方式。它衡量最坏情况下的时间复杂度或算法可能完成的最长时间。

例如，对于一个函数 f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

Ω符号，Ω

符号 Ω(n) 是表示算法运行时间下限的正式方式。它衡量最佳案例时间复杂度或算法可能完成的最佳时间量。

例如，对于一个函数 f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

θ符号，θ

符号 θ(n) 是表示算法运行时间的下限和上限的正式方式。它表示如下-

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

常用渐近符号

以下是一些常见的渐近符号列表-

常数	-	Ο(1)
对数	-	Ο(log n)
线性	-	Ο(n)
n log n	-	Ο(n log n)
二次元	-	Ο(n²)
立方	-	Ο(n³)
多项式	-	n^Ο(1)
指数	-	2^Ο(n)

找工作要求35岁以下，35岁以上的程序员都干什么去了？

长久以来，一直有一个问题困扰着技术人——如何打破“程序员的35岁职业魔咒”，这一天迟早会到来，或早或晚。

或许是选错了行业，程序员薪水虽高，但光鲜的外表下，背后的苦衷只有自己知道。三十多岁本该是一个人事业的黄金期，但技术变化日新月异，行业竞争异常残酷，对一个企业来说，永远有比你更年轻、劳动成本更低的人可以选择，这让你的中年危机提前到来。破局的智慧可以看看这本书！>>

<< 算法基础贪心算法 >>

昵称：邮箱：