algorithm - 如何为不同的符号 Big O、Omega、Litle o、Litle omega 和 Theta Notation 计算 "n"

Question

我正在研究算法，但是找到时间复杂度的计算对我来说并不是那么容易，很难记住什么时候使用 log n、n log n、n^2、n^3、2n 等，我的疑问是关于如何在计算复杂性时考虑这些输入函数，它们是否有任何特定的方法来计算复杂性，比如使用 for 循环总是需要这么多的复杂性等等……？

Answer 1

Log(n):当您使用递归并生成树时，请使用 log(n)。我的意思是，在 divide 和 conquer 中，当您将问题分解为 2-halfs 时，实际上您正在生成一个递归树 .

它的复杂度是Log(n)，为什么？因为它本质上是二叉树，对于二叉树，我们使用 Log(Base2)(n)。

自己尝试:假设 n=4(Elements) 所以 log(base2)(4)=2，你把它分成相等的一半。

nLog(n): 记住 Log(n) 它是除法直到单个元素。之后，您开始合并排序的元素，这需要liner time

换句话说，元素的合并具有复杂性"n"，因此总的复杂性将是n(Merging) + Log(n)(Dividing)，最终成为< strong>nLog(n).

n^2:当您看到一个问题在两个嵌套循环中得到解决时，复杂度为 n^2。即他们在 2 个循环中计算的矩阵/二维数组。一个循环在外层循环中。

n^3:哦，3 维数组，这是用于 3 个嵌套循环。循环内循环内循环。

2n:谢谢你没有忘记把这个“n”写成“2”，不然我忘了解释了。

所以这里的 "2" 和 "n" 是不变的，忽略它。为什么 ？。因为如果你乘飞机去其他城市。您将只计算飞行时间，而不是到达 AIR 港口所花费的时间。我的意思是这是次要的，我们删除常量。

对于“n”，只需记住这个词“线性”即Big-O(n)是线性复杂度。可悲的是，我发现没有算法可以在线性时间内对元素进行排序。即只在一个循环中。(单数组遍历)。

要记住的事情:

标称时间:线性时间，复杂度Big-O(n)

多项式时间: 非线性时间，复杂度 Big-O[ log(n), nlog(n), n^2, n^3, n^4, n^5).

指数时间: 2^n, n^n 即这个问题将在指数时间内解决，即 N^power(n) (这些都是坏坏坏，不叫算法)