2

我一直在自学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. 记录 n^3
  3. O((log^2)n)+O(n)
  4. 4^n
  5. n^3/2
4

2 回答 2

9

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

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

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

也就是说，询问具有一定复杂性的算法示例是很合理的；你已经列出了一些。为了解决您的问题：

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

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

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

于 2010-10-25T08:35:28.660 回答
-1

您给出的算法严格来说不是 Big-O 而是 Theta。Big-O 是一个渐近上界，这意味着在某些更坏的情况下输入运行时间将是给定的，但并非针对所有输入，因为 Theta 是一个紧界，意味着运行时间将始终如此。例如，考虑一个排序算法，它以一个已经排序的列表作为输入，或者一个搜索算法，其中要找到的东西是列表中的第一个元素（在这种情况下，二进制搜索与线性搜索相比如何）。

于 2010-10-25T08:45:09.440 回答