大O时间复杂度
我一直在自学 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++;
我遇到过这些我不太理解的符号。我如何在算法方面给出这些例子？
也许我应该这样表述：编写一个算法，其运行时间与以下比例成比例：
- O((n^3)/4)
- log n^3
- O((log^2)n)+O(n)
- 4^n
- n^3/2
I have been doing some self-study on Big-O. I understand how to give examples of the following notations to algorithms:
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++;
I have come across these notations which I don't quite comprehend. How do I give examples of these in terms of algorithms?
Maybe I should phrase it this way: write an algorithm which takes running time in proportion to:
- O((n^3)/4)
- log n^3
- O((log^2)n)+O(n)
- 4^n
- n^3/2
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
严格来说，您给出的算法不是 Big-O，而是 Theta。 Big-O 是一个渐近上限，这意味着在某些最坏情况的输入上，运行时间将是给定的，但不适用于所有输入，而 Theta 是一个紧界，意味着运行时间将始终如此。例如，考虑一个排序算法，它给出一个已经排序的列表作为输入，或者一个搜索算法，其中要找到的东西是列表中的第一个元素（在这种情况下，二进制搜索与线性搜索相比如何）。
The algorithms you have given are strictly speaking not Big-O but Theta. Big-O is an asymptotic upper bound meaning that on some worse case input the running time will be the one given but isn't for all inputs, where as Theta is a tight bound meaning that the running time will always be that. Consider for instance a sorting algorithm that is given an already sorted list as input, or a search algorithm where the things to be found is the first element in a list (how does binarysearch compare to linear search in this case).
我担心您误解了“Big-O”符号。
符号并不是“表达”为算法。相反，Big-O 表示法描述了算法的属性。
所以不是“O(N)可以表示为XXX”，而是“算法XXX的复杂度为O(N)”。
也就是说，要求提供具有一定复杂度的算法示例是相当合理的；
你已经列出了一些。解决您的问题：
O(4^n) 与 O(e^n) 相同，通常写为 O(exp(n)) （尝试理解为什么它是相同的）。O(4^n) 属于具有“指数复杂度”的算法类 (EXPTIME)。数学/计算机科学中的许多重要问题都具有指数复杂性（或接近指数复杂性）。例如，具有指数复杂度的算法是离散对数问题的简单解决方案。
对于其他复杂性，我无法给出示例，但您可能会通过谷歌搜索找到一个示例。
I fear you are misunderstanding "Big-O" notation.
A notation is not "expressed" as an algorithm. Rather, the Big-O notation describes a property of an algorithm.
So it's not "O(N) can be expressed as XXX", but rather "algorithm XXX has complexity of O(N)".
That said, it is quite reasonable to ask for examples of algorithms with a certain complexity;
you already list some. To address your questions:
O(4^n) is the same as O(e^n), often written as O(exp(n)) (try to understand why it is the same).O(4^n) belongs to the class of algorithms with "exponential complexity" (EXPTIME). Many important problems in math/CS have exponential complexity (or nearly exponential complexity).An algorithm with exponential complexity would be for example a naive solution to the discrete logarithm problem.
For the other complexities I cannot give an example, but you will probably find one by googling a bit.