少年阿賓

          那些青春的歲月

            BlogJava :: 首頁 :: 聯系 :: 聚合  :: 管理
            500 Posts :: 0 Stories :: 135 Comments :: 0 Trackbacks

          二分查找的基本思想是將n個元素分成大致相等的兩部分,去a[n/2]與x做比較,如果x=a[n/2],則找到x,算法中止;如果x<a[n/2],則只要在數組a的左半部分繼續搜索x,如果x>a[n/2],則只要在數組a的右半部搜索x.

          時間復雜度無非就是while循環的次數!

          總共有n個元素,

          漸漸跟下去就是n,n/2,n/4,....n/2^k,其中k就是循環的次數

          由于你n/2^k取整后>=1

          即令n/2^k=1

          可得k=log2n,(是以2為底,n的對數)

          所以時間復雜度可以表示O()=O(logn)

          posted on 2015-03-26 16:30 abin 閱讀(641) 評論(0)  編輯  收藏 所屬分類: algorithm
          主站蜘蛛池模板: 藁城市| 南投市| 灵川县| 湖州市| 三明市| 武定县| 河北区| 加查县| 景洪市| 隆子县| 桃园市| 贵阳市| 澳门| 上林县| 临沧市| 米泉市| 定结县| 慈利县| 义马市| 阳信县| 高阳县| 沙坪坝区| 班戈县| 吉木萨尔县| 罗平县| 平舆县| 通许县| 商南县| 长葛市| 台南市| 勃利县| 申扎县| 静海县| 大丰市| 永顺县| 同心县| 神池县| 敦化市| 武夷山市| 那坡县| 阆中市|