algorithm - 文字列の順序付き配列 - 最悪の場合?

Question

O(log n)は、長さ n の文字列の順序付き配列に制限された最悪の場合の検索時間でしょうか?

今日テストをしたところ、私が正しいか間違っているか疑問に思って、これらを選択しました...

• の上）
• O(ログ n)
• O(n/2)
• O(√n)

編集：この質問を編集して、物事を明確にしました。

Answer 1

並べ替えられた文字列の配列で文字列を検索すると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).

Answer 2

順次検索:

最良:O(n) 最悪:O(n)

二分探索:

最良:O(1) 最悪:O(log n)