arrays - 有序数组大 o 表示法

Question

我只是有一个简单的问题，为什么排序数组 O(log N) 的大 O 表示法是 O(log N)？它将是一个排序数组。

score 4 · Accepted Answer

这个问题有点假。复杂性不适用于数组，但实际上适用于对数组进行排序的算法（我假设您的意思是运行时复杂性而不是内存）。

因此，根据所使用的算法，用于对数组进行排序的 O(X) 中的 X 可能会有很大差异。

检查这些页面以了解一般复杂性和特殊情况下的数组排序。

score 4 · Accepted Answer

大 O 符号通常在算法的上下文中有意义。当你说大 O 表示法是 O(log n) 时，你在考虑什么操作。

如果您的意思是搜索，那么它是 O(log n)，因为您可以使用二进制搜索。这实质上意味着您查看数组的中间元素，如果它大于您要搜索的元素，则搜索较大的一半（以相同的方式），反之亦然（假设您还没有当然找到了你的元素）。您可以在wikipedia上阅读更详细的说明。

在搜索的每一步（查看中间元素），您都将必须搜索的数组大小减半，因为您现在可以知道您的搜索元素必须位于中间元素的哪一侧。当然，这只适用于排序数组。对于未排序的数组，您可以使用的唯一搜索算法是线性搜索，您可以在其中检查数组中的每个元素，这将平均进行 n/2 次检查。

一般来说，大O描述的是算法的运行时特性，所以不能只问，排序数组的大O是什么，一定是对数组的一些操作。但是，您可以根据某些数据结构占用的空间（内存）来考虑 Big O。在这种情况下，排序数组仍然需要 O(n) 空间来存储 N 个元素。

2 回答 2