java - 大O时间复杂度

Question

我一直在自学 Big-O。我了解如何为算法提供以下符号的示例:

O(N):

for(int i = 0; i < n; i++)
    sum++;

O(N^2):

for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O(N^3):

for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

我遇到过这些我不太理解的符号。我如何在算法方面给出这些示例？

也许我应该这样表述:编写一个算法，其运行时间与以下比例成比例:

1. O((n^3)/4)
2. 对数n^3
3. O((log^2)n)+O(n)
4. 4^n
5. n^3/2

Answer 1

我担心您误解了“Big-O”符号。

符号并不是“表达”为算法。相反，Big-O 表示法描述了算法的属性。

所以不是“O(N)可以表示为XXX”，而是“算法XXX的复杂度为O(N)”。

也就是说，要求提供具有一定复杂度的算法示例是相当合理的；你已经列出了一些。解决您的问题:

O(4^n) 与 O(e^n) 相同，通常写为 O(exp(n))(尝试理解为什么它是相同的)。 O( 4^n) 属于具有“指数复杂度”的算法类别 ( EXPTIME )。数学/计算机科学中的许多重要问题都具有指数复杂性(或接近指数复杂性)。

具有指数复杂度的算法可能是 discrete logarithm problem 的简单解决方案。 .

对于其他复杂性，我无法给出示例，但您可能会通过谷歌搜索找到一个示例。