search - nxn 行列の検索

Question

答えを確認して、もっと速い方法がないか確認したかっただけです。

並べ替えられた nxn 行列があった場合、それを検索する最良の方法は何ですか?また、その複雑さは何ですか? - 行を二分検索してから、列を二分検索します。O(logN)。

並べ替えられた行と並べ替えられていない列を含む nxn 行列があった場合、それを検索する最良の方法とその複雑さは何ですか? - 行をバイナリ検索してから、列を線形検索します。オン）。

Answer 1

行列に対する並べ替えの意味を定義し、検索対象を定義します。おそらく例を追加します。

より明確にするために、これはソートされていますか（1）：

1 6
4 5

または、これはソートされていますか(2):

1 4
5 6

そして、検索とはどういう意味ですか。マトリックス全体で単一の値を見つけたいですか (a)、すべての行で単一の値を見つけたいですか (b)、またはすべての行で異なる値を見つけたいですか (c)?

---

(1)(a) の場合、n*log(n) (n 検索、行ごとに 1 つ)

(2)(a) の場合、log(n) (1 つの大きな行として表示されるため、log(n*n) => log(n^2) => 2*log(n) => log(n)

---

(1)(b) の場合、n*log(n) (n 検索、行ごとに 1 つ)

(2)(b)の場合はlog(n)

---

(1)(c) の場合、n*log(n) (n 検索、行ごとに 1 つ)

(2)(c) の場合、少なくとも n*log(n) ですが、おそらく値をソートし、あらかじめソートされた行列を使用して、log(n) または log(n)*log(n) で実行できます。これはさらに分析する必要があります

---

いくつかの基本的な考えに基づいているだけで、証明のないすべて。