二分法的遞歸算法的時(shí)間復(fù)雜度是O（n^2）么？二分法，無論是否遞歸，都是O（log2n）。每次比較時(shí)，搜索范圍都縮短到原來的1/2。數(shù)組排序的最少時(shí)間復(fù)雜度O(nlog2n)怎么計(jì)算的？二分法的基本思

二分法的遞歸算法的時(shí)間復(fù)雜度是O（n^2）么？

二分法，無論是否遞歸，都是O（log2n）。每次比較時(shí)，搜索范圍都縮短到原來的1/2。

數(shù)組排序的最少時(shí)間復(fù)雜度O(nlog2n)怎么計(jì)算的？

二分法的基本思想如下：假設(shè)數(shù)據(jù)按升序排序。對(duì)于給定的值x，從序列的中間位置開始。如果當(dāng)前位置值等于x，則搜索成功；如果x小于當(dāng)前位置值，則搜索在序列的前半部分；如果x大于當(dāng)前位置值，則搜索在序列的后半部分繼續(xù)，直到找到為止。因?yàn)閿?shù)組是預(yù)先排序的，所以我們可以使用半查詢的方法，每次都丟棄一半要查詢的部分。這樣，長(zhǎng)度為n的數(shù)組只需要log2n查詢，2是對(duì)數(shù)的基。例如，長(zhǎng)度為7的數(shù)組最多只能找到三次。O（log2n）只表示它與log2n的數(shù)量級(jí)相同，因?yàn)榇嬖谏崛雴栴}，也有可能是在查詢過程中發(fā)現(xiàn)的（即半個(gè)查詢點(diǎn)正好是要查詢的數(shù)據(jù)），所以O(shè)（log2n）是一個(gè)上限