我只是想确认我的答案，看看是否有更快的方法。
如果有一个已排序的 nxn 矩阵，那么搜索它的最佳方法是什么，它的复杂性是多少？- 对行进行二进制搜索，然后对列进行二进制搜索。O(logN)。
如果有一个 nxn 矩阵，其中行已排序，列未排序，那么搜索它的最佳方法是什么，它的复杂性是多少？- 二进制搜索行，然后线性搜索列。上）。
问问题
462 次
1 回答
1
定义排序在矩阵上的含义并定义您要搜索的内容。也许添加一个例子。
为了更清楚，这是排序的（1）：
1 6
4 5
或者这是排序的（2）：
1 4
5 6
而且，搜索是什么意思。您想在整个矩阵中找到一个值（a），在每一行中找到一个值（b），还是在每一行中找到一个不同的值（c）？
对于 (1)(a)，它是 n*log(n)（n 次搜索，每行一个）
对于 (2)(a) 它是 log(n) （将其视为一大行，所以 log(n*n) => log(n^2) => 2*log(n) => log(n)
对于 (1)(b) 它是 n*log(n) （n 次搜索，每行一个）
对于 (2)(b)，它是 log(n)
对于 (1)(c) 它是 n*log(n) （n 次搜索，每行一个）
对于 (2)(c)，它至少是 n*log(n)，但可能您可以对值进行排序并使用预排序矩阵在 log(n) 或 log(n)*log(n) 中完成，这需要进一步分析
一切都没有证明，只是基于一些基本的想法。
于 2012-10-29T15:53:43.233 回答