algorithm - 与大O比较和对比

Question

谁能解释对空间复杂度的理解？在您自己看来，在设计算法时，哪种复杂性（时间或空间）更重要？

O(log2N)和有什么区别O(Nlog2N)？我观看了有关它的各种视频，但仍然不完全理解。

标签： algorithmdata-structuresbig-o

Answer 1

根据定义，如果 f 和 g 是实数 x 的正函数，“g is O(f(x))”意味着存在一些 X 和一些 M，使得对于所有 x > X：g(x) <= M * f （X）

您可以用自然 n 替换实数 x 并获得相同的定义。

在实践中，假设您有一些数组（列表、向量）并且您有一些任务。

假设数字数组是有序的，您需要找到一个特定的数字。因此，您检查数组的中间，而不是将获得的数字与需要查找的数字进行比较，然后检查数组的中部或上半部或下半部。然后你继续直到你找到证明没有这个数字的数字。尝试次数将接近 log2(n)，因此您可以说时间是 O(log N)，因为 O(log2 N) 是相同的。

如果您逐个遍历数组，则必须检查所有元素，时间将为 O(n)。假设您有一百万个元素。然后在二进制搜索中你需要大约 20 次检查，在完整循环中你需要百万。这就是为什么 O(log N) 和 O(N) 之间的差异至关重要的原因。

另一个例子，你需要对一个数组进行排序（排序）。您可以通过检查所有元素来找到最小元素。然后你通过检查所有期望的第一个来找到第二个最小值，然后你继续直到你得到最大的元素。数字计算为 n + (n - 1) + ... + 2 + 1 = n (n + 1) / 2 即 O (n^2)。

您还可以使用快速排序算法，将二进制搜索和所有元素的完整循环结合起来。在这种情况下，时间将为 O (n * log n)

现在假设您在数组中有一百万个元素。如果您使用第一种方法对数组进行排序，则时间将接近 (10^6)^2 = 10^12 = 1,000,000,000,000 次操作（实际数量会更少，但只计算幂）。第二种方法将给出 10^6 * log(10^6) 的结果，大约为 10^6 * 10 = 10,000,000（实际数字也将是 20,000,000，我们在检查 big-O 时不计算在内）。看到不同。

同样的空间问题。假设您需要对用户（输入文件）的输入值做一些事情，而您别无选择，只能将所有值保存在内存中。在这种情况下，您需要 O(n) 内存。但是，如果您找到的解决方案不是将所有值都保存在内存中，而只是将当前输入值和其他一些技术变量保存在内存中，那么您会说您需要 O(1) 的内存。只需将数百万字节与几个字节进行比较，即可了解它的重要性。

不需要完整数组的任务示例是输入文件中给出的所有值的最后 2 位乘积。您不需要为完整的值列表保留内存。