python中的时间和空间分析

Question

有人可以提供时间和空间的 O(log(n)) 和 O(nlog(n)) 问题的示例吗？

我对这种类型的分析很陌生，看不到过去的多项式时间/空间。

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

此外，我将不胜感激任何涵盖这些情况（时间和空间）的优秀示例：

我发现空间分析有点模棱两可，因此与同一地点的时间分析中的其他案例相比，看到它会很高兴 - 我无法在网上可靠地找到它。

您能否在空间和时间分析中为每个案例提供示例？

Answer 1

在示例之前，对大 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_t, thenabs(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 的书。