algorithm - 算法复杂度的大哦符号

Question

如果 N*C*(logN +N) 表示算法 1 的计算时间步长，N*C*(logN +N*C) 表示算法 2 的计算时间步长，那么说两者的计算复杂度为O(N^2)?

*其中 C 是一个常数值

score 1 · Accepted Answer

是的，这是我的逻辑：

O(Cn(log n + Cn))

移除常量

= O(n(log n + n))

分裂乘法

= O(n * log n + n^2)

删除较小的术语

= O(n^2)

是否“非常大”无关紧要C，我们只关心nBig-O 表示法，因为它是一个不断增长的术语。当 n 变得足够大（例如接近无穷大）时，C将变得毫无意义。在实践C中可能会产生巨大的影响，但这在 Big-O 中被抽象出来了。

score 1 · Accepted Answer

是的，这是正确的，因为 f \element O(g) ( Landau -Notation) 意味着您的算法f增加得比g慢。由于您的两种算法的增长速度都比 n^2 慢，因此您的假设是正确的。

Wrt 常量 - 让我描述一下:)

说明复杂度为O(n^2)意味着您可以看到从 nlog(n) 到 n^2 的整个平面。那就是你忽略常数的地方。所以你的算法a可以比算法b好得多，但仍然保持相同的朗道复杂度，因为这只给出了一个上限。

在此处输入图像描述

score 0 · Accepted Answer

是的，将步数乘以一个常数对 Big-Oh 复杂度表示法没有影响。

此外，随着 N 变大，N ²项在 N log(N) 上占主导地位，这就是 Big-Oh 表示法旨在传达的内容。

score -1 · Accepted Answer

要记住的一件事.. c 值起着重要作用..

假设一个算法在一个数组上运行了大约 32 次。

所以算法的复杂度是 32*n = C*n = O(n)

让我们尝试在大小为 30 的数组上运行算法。所以它的 32*30 。这是 n^2 操作。

我们通常为大集合计算大 O 分析..真的很大.所以它是有道理的

来回答你的问题。

只要您的常数 C 具有可比性，它们都在 O(n^2) 中运行。所以这取决于算法

4 回答 4