想改善这个问题吗？更新问题，使其仅通过editing this post专注于一个问题。
6个月前关闭。
Improve this question
有人可以提供一个关于时间和空间的O（log（n））和O（nlog（n））问题的例子吗？
我对这种类型的分析很陌生，看不到过去的多项式时间/空间。
我不明白的是你怎么能成为O（1） 像“半恒定”？
此外，我很高兴看到涉及这些案例（时间和空间）的出色示例：
我发现空间分析有点含糊不清，因此与在同一地点进行时间分析的其他情况相比，很高兴看到它–我在网上找不到可靠的信息。
您能否在时空上为每种情况提供示例？
分析？
最佳答案
在示例之前，对大O符号进行一些澄清
也许我弄错了，但是看到
我不明白的是，你如何成为O（1）
让我认为您已将big-O表示法的概念介绍为要进行的操作数（或要存储的字节数等），例如如果有循环for(int i=0;i<n;++i)，则有n个操作，因此时间复杂度为O(n)。尽管这是一个很好的第一眼直觉，但我认为这可能会引起误解，因为big-O表示法定义了更高的渐近边界。
假设您选择了一种对数字数组进行排序的算法，并表示x该数组中元素的数量和f(x)该算法的时间复杂度。现在假设我们说算法是O(g(x))。这意味着随着x的增长，我们最终将达到阈值x_t，因此，如果x_i>x_t，则abs(f(x_i))始终小于或等于alpha*g(x_i)，其中alpha是事后实数。
结果，O(1)函数并不总是需要相同的恒定时间，而是可以确保无论需要多少数据，完成任务所需的时间都将小于恒定的时间，例如5秒。同样，O(log(n))并不意味着有任何半常数的概念。这仅意味着1）算法将花费的时间将取决于您输入它的数据集的大小，并且2）如果数据集足够大（即n足够大），则它将花费的时间完成它总是小于或等于log(n)。
有关时间复杂度的一些示例O(1)：从数组访问元素。O(log(n))：binary search以增量排序的数组。假设您有一个n元素数组，并且想找到值等于x的索引。您可以从数组的中间开始，如果在其中读取的值v大于x，则在v的左侧重复相同的过程，如果较小，则请看v的右侧。您继续此过程，直到找到所需的值。如您所见，如果幸运的话，您可以在第一次尝试时在数组中间找到值，也可以在log(n)操作之后找到它。因此，没有半恒定性，Big-O表示法告诉您最坏的情况。O(nlogn)：使用Heap sort对数组进行排序。在这里解释太久了。O(n^2)：计算正方形灰度图像上的所有像素的总和（您可以将其视为二维数字矩阵）。O(n^3)：天真地将两个大小为n*n的矩阵相乘。O(n^{2+epsilon})：以智能方式相乘矩阵（see wikipedia）O(n!)天真地计算阶乘。
有关空间复杂性的一些示例O(1)堆排序。有人可能会认为，由于需要从树的根中删除变量，因此将需要额外的空间。但是，由于堆只能作为数组实现，因此您可以将删除的值存储在该数组的末尾，而不用分配新的空间。
我认为，一个有趣的示例是比较一个经典问题的两种解决方案：假设您有一个整数数组X和一个目标值T，并且确保了存在两个值x,y中的>。您的目标是找到这两个值。
一种解决方案（称为两指针）是使用heapsort（X space）对数组进行排序，然后定义两个索引x+y==T，分别指向已排序数组O(1)的开始和结束。然后，如果i,j，我们增加X_sorted，如果X[i]+X[j]<T，我们减少i。我们在X[i]+X[j]>T时停止。显然，这不需要额外的分配，因此该解决方案具有j的空间复杂度。第二种解决方案是：
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
由于字典的原因，其空间复杂度
X[i]+X[j]==T。上面给出的时间复杂度示例很简单（除了关于有效矩阵乘法的示例）。正如其他人所说，我认为阅读有关该主题的书是您深入理解该主题的最佳选择。我强烈建议Cormen's book。
关于python - python中的时空分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59114193/