大时间的复杂性

Question

我一直在做Big-O的自学.我理解如何给算法提供以下符号的示例:

上):

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. log n ^ 3
3. O((日志^ 2)N)+ O(n)的
4. 4 ^ N
5. N R个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)的算法类.数学/ CS中的许多重要问题具有指数复杂性(或几乎指数复杂性).

具有指数复杂度的算法将是例如离散对数问题的简单解决方案.

对于其他复杂性我不能举一个例子,但你可能会通过谷歌搜索找到一个.