algorithm - 有序的字符串数组 - 最坏的情况？

Question

O(log n)是否会是限制在长度为 n 的有序字符串数组的最坏情况搜索时间？

我今天刚做了一个测试，我想知道我是对还是错，选择这些......

• 上）
• O(log n)
• O(n/2)
• O(√n)

编辑：我编辑了这个问题以使事情更清楚。

Answer 1

顺序搜索：

最佳：O(n) 最差：O(n)

二进制搜索：

最佳：O(1) 最差：O(log n)

Answer 2

在排序的字符串数组中搜索字符串将是字符串O(|S| * logn)的|S|平均长度，并且n是字符串的数量，使用二进制搜索，因为它具有O(logn)比较操作，并且每个比较都是O(|S|)（它必须读取字符串.. .)

如果您将字符串的长度视为常量 - 它是O(logn). 在谈论字符串时，通常不会采用这种假设。

请注意，还有其他数据结构 - 例如trie，可以实现更好的复杂性。Trie 允许O(|S|)搜索集合中的每个字符串。

PS
从数学上讲，由于大 O 表示法是一个上限，而不是一个紧界 -对于二分搜索，所有答案都是正确的¹，它是O(n), O(n/2), O(logn), O(sqrt(n))，因为它们都为二分搜索提供了渐近上限。

---

(1) 假设二分查找并且所有字符串都有长度限制，所以每个比较操作都是O(1).