log(n) means logarithmic growth. An example would be divide and conquer algorithms. If you have 1000 sorted numbers in an array ( ex. 3, 10, 34, 244, 1203 ... ) and want to search for a number in the list (find its position), you could start with checking the value of the number at index 500. If it is lower than what you seek, jump to 750. If it is higher than what you seek, jump to 250. Then you repeat the process until you find your value (and key). Every time we jump half the search space, we can cull away testing many other values since we know the number 3004 can't be above number 5000 (remember, it is a sorted list).

N log(N)表示N * log(N)

我喜欢don neufeld的答案，但我想我可以加上O(nlog n)

使用简单分治策略的算法可能是O(log n)最简单的例子是在排序列表中查找某个东西。你不需要从头开始扫描。你走到中间，你决定是向后走还是向前走，跳到中途，直到你找到你要找的东西。

如果您查看快速排序或归并排序算法，您将看到它们都采用将列表分成两半，对每一半排序(使用相同的算法，递归地)，然后重新组合两半的方法。这种递归分治策略是O(nlog n)

If you think about it carefully, you'll see that quicksort does an O(n) partitioning algorithm on the whole n items, then an O(n) partitioning twice on n/2 items, then 4 times on n/4 items, etc... until you get to an n partitions on 1 item (which is degenerate). The number of times you divide n in half to get to 1 is approximately log n, and each step is O(n), so recursive divide and conquer is O(n log n). Mergesort builds the other way, starting with n recombinations of 1 item, and finishing with 1 recombination of n items, where the recombination of two sorted lists is O(n).

至于抽大麻写一个O(n!)算法，除非你别无选择。上面提到的旅行推销员问题被认为是这样一个问题。

要理解O(n log n)，请记住log n意味着log-base-2 (n)。然后看看每一部分:

O(n)是，当你对集合中的每一项进行操作时。

O(log n)是指操作的次数与取2的指数相同，以得到项目的数量。例如，二分搜索必须将集合切成log n的一半。

O(nlogn)是一个组合——你在对集合中的每一项进行二分搜索。高效的排序通常是对每个项目进行一次循环，并在每个循环中进行良好的搜索，以找到放置相关项目或组的正确位置。因此是n * log n。

为了对被问到的问题保持真诚，我会用回答8岁孩子的方式来回答这个问题

假设一个冰淇淋小贩准备了许多不同形状的冰淇淋(比如N个)，按顺序排列。 你想吃中间的冰淇淋

情况1:只有吃完所有比它小的冰淇淋，你才能吃冰淇淋 你将不得不吃掉一半准备好的冰淇淋(输入)。答案直接取决于输入的大小 解是o(N)阶的

情况2:—你可以直接吃中间的冰淇淋

解是O(1)

情况3:只有当你吃完所有比它小的冰淇淋时，你才能吃冰淇淋，每次你吃冰淇淋时，你都允许另一个孩子(每次都是新孩子)吃掉他所有的冰淇淋 总时间为N + N + N.......(N/2)次 溶液是O(N2)

把它想象成垂直堆叠乐高积木(n)，然后跳过它们。

O(1)表示在每一步，你什么都不做。高度保持不变。

O(n)表示在每一步，你堆叠c块，其中c1是常数。

O(n²)表示在每一步，你堆叠c2 x n个块，其中c2是一个常数，n是堆叠块的数量。

O(nlogn)表示在每一步，你堆叠c3 x n x logn个块，其中c3是一个常数，n是堆叠块的数量。

不，O(n)算法并不意味着它将对每个元素执行操作。大o符号给了你一种方法来谈论你的算法的“速度”独立于你的实际机器。

O(n)表示算法花费的时间随着输入的增加而线性增长。O(n²)意味着你的算法花费的时间是你输入的平方。等等。