在示例之前，对大 O 表示法的一点说明

也许我错了，但看到

我不明白的是你怎么能成为 O(1) < O(log(n)) < O(n) 这就像“半常数”？

让我认为您已经了解了big-O符号的概念，即要进行的操作数（或要存储的字节数等），例如，如果您有一个循环for(int i=0;i<n;++i)，那么就有n操作，因此时间复杂度为O(n). 虽然这是一个很好的第一直觉，但我认为它可能会产生误导，因为大 O 表示法定义了更高的渐近界。

假设您选择了一种算法来对数字数组进行排序，让我们表示x该数组中元素的数量，以及f(x)该算法的时间复杂度。现在假设我们说算法是O(g(x))。这意味着随着x增长，我们最终将达到一个阈值x_t，即如果, x_i>x_tthenabs(f(x_i))将始终低于或等于正数实数。alpha*g(x_i)alpha

因此，一个函数O(1)并不总是花费相同的恒定时间，相反，您可以确定无论它需要多少数据，完成其任务所需的时间都将低于恒定数量的时间，例如 5秒。同样，O(log(n))并不意味着有任何半常数的概念。这只是意味着 1）算法将花费的时间将取决于您提供给它的数据集的大小，以及 2）如果数据集足够大（即 n足够大），那么它完成所需的时间is 将始终小于或等于log(n)。

关于时间复杂度的一些例子

O(1): 访问数组中的元素。
O(log(n))：在增量排序的数组中进行二进制搜索。假设您有一个n元素数组，并且您想要找到值等于的索引x。您可以从数组的中间开始，如果v您读取的值大于x，则在的左侧重复相同的过程v，如果较小，则查看的右侧v。您继续此过程，直到找到您要查找的值。如您所见，如果幸运的话，您可以在第一次尝试时找到数组中间的值，也可以在log(n)操作后找到它。所以不存在半常数，Big-O 表示法告诉你最坏的情况。
O(nlogn)：使用堆排序对数组进行排序。在这里解释有点太长了。
O(n^2)：计算正方形灰度图像上所有像素的总和（您可以将其视为二维数字矩阵）。
O(n^3)：天真地乘以两个大小矩阵n*n。
O(n^{2+epsilon})：以聪明的方式乘法矩阵（见维基百科）
O(n!)天真地计算阶乘。

关于空间复杂度的一些例子

O(1)堆排序。有人可能会认为，由于您需要从树的根中删除变量，因此您将需要额外的空间。但是，由于堆只能实现为数组，因此您可以将删除的值存储在所述数组的末尾，而不是分配新空间。
我认为，一个有趣的例子是比较一个经典问题的两个解决方案：假设你有一个X整数数组和一个目标值T，并且你被保证存在x,y这样X的两个值x+y==T。您的目标是找到这两个值。一种解决方案（称为双指针）是使用 heapsort ( O(1)space) 对数组进行排序，然后定义两个索引i,j，分别指向已排序数组的开始和结束X_sorted。然后，如果X[i]+X[j]<T，我们增加i，如果X[i]+X[j]>T，我们减少j。我们在时停止X[i]+X[j]==T。很明显，这不需要额外的分配，因此解决方案具有O(1)空间复杂性。第二种解决方案是：
```
D={}
for i in range(len(X)):
    D[T-X[i]]=i
for x in X:
    y=T-x
    if y in D:
        return X[D[y]],x
```
O(n)由于字典，它具有空间复杂性。

上面给出的时间复杂度的例子（除了关于有效矩阵乘法的例子）非常简单。正如其他人所说，我认为阅读有关该主题的书是深入理解该主题的最佳选择。我强烈推荐Cormen 的书。

python - python中的时间和空间分析

问题描述

解决方案

在示例之前，对大 O 表示法的一点说明

关于时间复杂度的一些例子

关于空间复杂度的一些例子

推荐阅读