首頁>Club>
5
回覆列表
  • 1 # 昭然如磐

    其實就是一種透過不斷的排除不可能的東西,來最終找到需要的東西的一種方法.所以可以理解成排除法。

    之所以叫二分,是因為每次排除都把所有的情況分成"可能"和"不可能"兩種,然後拋棄所有"不可能"的情況。

    最正統的二分法中,是每次排除都可以排除掉一半的情況,這樣子的尋找效率是很高的。

    比如要在1-100的數字中詢問出某一個特定的數字,我可以先問,這個數字是否大於50?這樣無論是或者不是,我都可以排除掉一半的數字(50之前的被排除,或者50之後的被排除)。假如回答不是,接著我可以問是否大於25?又可以排除掉一半。這樣下去,很快就會排除剩下一個數字,即是要找的那個。

    要理解這種方法為什麼這麼快需要用一點數學計算,很顯然最理想的二分法是每次把情況除以2,而逐個檢查的方法是把情況減1,這個排除的速度比較只要稍微計算一下就可以有認識。

    另外就是二分法不一定真的是平均二分,對於不平均的二分法,最極端的情況下,每次可能只能排除一種情況,這樣就和逐個排查沒有區別了。這叫做二分法的退化,是使用二分法的時候需要想辦法避免的。

  • 中秋節和大豐收的關聯?
  • 生吃洋蔥的功效與作用有什麼呢?