我正在研究N元素中二元搜索，三元搜索和k元搜索的时间复杂度，并且已经提出了它各自的渐近更差的运行时间 . 但是，我开始想知道如果我将N个元素分成n个范围（或者n个n元素中的n元搜索）会发生什么 . 这是一个数组中的排序线性搜索，它会导致O（N）的运行时间？这有点令人困惑 . 请帮帮我！
你说的是对的 .
对于 k-ary 搜索，我们有：
k-ary
执行 k-1 检查边界以隔离其中一个 k 范围 .
k-1
k
跳到从上面获得的范围 .
因此，时间复杂度基本上是 O((k-1)*log_k(N)) ，其中 log_k(N) 表示“ log(N) 到基础 k ” . k=2 时最小 .
O((k-1)*log_k(N))
log_k(N)
log(N)
k=2
如果 k = N ，时间复杂度将为： O((N-1) * log_N(N)) = O(N-1) = O(N) ，这与线性搜索在算法和复杂性方面相同 .
k = N
O((N-1) * log_N(N))
O(N-1)
O(N)
翻译成上面的算法，它是：
执行 N-1 检查边界（每个第一个 N-1 元素）以隔离其中一个 N 范围 . 这与第一个 N-1 元素中的 linear search 相同 .
N-1
N
跳到从上面获得的范围 . 这与检查最后一个元素（在恒定时间内）相同 .
1 回答
你说的是对的 .
对于
k-ary搜索，我们有：执行
k-1检查边界以隔离其中一个k范围 .跳到从上面获得的范围 .
因此，时间复杂度基本上是
O((k-1)*log_k(N))，其中log_k(N)表示“log(N)到基础k” .k=2时最小 .如果
k = N，时间复杂度将为：O((N-1) * log_N(N))=O(N-1)=O(N)，这与线性搜索在算法和复杂性方面相同 .翻译成上面的算法，它是：
执行
N-1检查边界（每个第一个N-1元素）以隔离其中一个N范围 . 这与第一个N-1元素中的 linear search 相同 .跳到从上面获得的范围 . 这与检查最后一个元素（在恒定时间内）相同 .