我只是想确认我的答案,看看是否有更快的方法.
如果有一个已排序的 nxn 矩阵,那么搜索它的最佳方法是什么,它的复杂性是多少?- 对行进行二进制搜索,然后对列进行二进制搜索.O(logN).
如果有一个 nxn 矩阵,其中行已排序,列未排序,那么搜索它的最佳方法是什么,它的复杂性是多少?- 二进制搜索行,然后线性搜索列.上).
searchtimematrixcomplexity-theory
定义排序在矩阵上的含义并定义您要搜索的内容.也许添加一个例子.
而且,搜索是什么意思.您想在整个矩阵中找到一个值(a),在每一行中找到一个值(b),还是在每一行中找到一个不同的值(c)?
一切都没有证明,只是基于一些基本的想法.