我已经理解O（logn）在某种意义上它会迅速增加但是随着输入的增加，增加的速度会延迟。我无法完全理解
我可以使用电话簿示例的修改和/或一些基本的python代码来理解这两个查询
你怎么看待O(n ^ 2)？就个人而言，我喜欢把它想象为O(n)工作O(n)次。
一个人为的O(n ^ 2)算法将迭代0, 1, ..., n - 1中的所有数字对
def print_pairs(n):
for i in range(n):
for j in range(i + 1, n):
print('({},{})'.format(i, j))
使用与上面类似的逻辑，你可以做O(log n)工作O(n)次，并具有时间复杂度O(n log n)。
例如，我们将使用二进制搜索来查找数组中元素的所有索引。
是的，我理解这是一个愚蠢的例子，但在这里我不想专注于算法的有用性而是复杂性。为了我们算法的正确性，我们假设输入数组已经排序。否则，我们的二进制搜索不能按预期工作，并且可能无限期地运行。
def find_indices(arr):
indices = []
for num in arr:
index = binary_search(arr, 0, len(arr), num)
indices.append(index)
return indices
def binary_search(arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l)/2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binary_search(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binary_search(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
至于你的第二个问题，肯定的是，log n << n为n倾向于无穷大
O(n + log n) = O(n)
从理论上讲，log n与n相形见绌，因为我们得到的任意大，所以我们不会将它包含在我们的Big O分析中。
与练习并列，如果您的算法遇到性能和/或缩放问题，您可能需要考虑这个额外的log n工作。
log n是一个比n慢得多的增长功能。当计算机科学家谈到big-O时，他们对极大输入值的函数增长感兴趣。函数在一些小数或拐点附近的作用是无关紧要的。
许多常见算法具有n log n的时间复杂度。例如，merge sort要求n步骤采用log_2(n)次，因为输入数据被分成两半。在研究算法之后，其复杂性为n log n的事实可能会通过直觉找到你，但你可以通过研究描述（递归）算法的递归关系得出相同的结论 - 在这种情况下T(n) = 2 * T(n / 2) + n。更一般但也许最不直观的是，master theorem可用于达到这个n log n表达式。简而言之，如果某些算法具有一定的运行时间并不是立即显而易见的话，请不要感到害怕 - 您可以通过多种方式来进行分析。
关于“复杂度n + log n”，这不是大O符号倾向于使用的方式。你可能有一个算法使n + log n工作，但我们称之为O(n + log n)，而不是称为O(n)，因为n比log n增长得快得多，因为log n术语可以忽略不计。 big-O的观点是仅说明增长最快的术语的增长率。
与n log n相比，log n更快。如果log n是将项目插入自平衡搜索树的时间复杂度，则n log n将n项目插入此类结构中的复杂性。
有一本Grokking algorithms很棒的书，它解释了算法复杂性检测（以及其他事情），并且通过一种非常简单的语言来解释。
从技术上讲，复杂度为O（n + log n）和复杂度为O（n）的算法是相同的，因为当n增长时，log n项变得可以忽略不计。
O（n）线性增长。斜率是恒定的。
O（n log n）超线性增长。斜率增加（缓慢）。