少年阿賓

          那些青春的歲月

            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 閱讀(634) 評論(0)  編輯  收藏 所屬分類: algorithm
          主站蜘蛛池模板: 溆浦县| 兴化市| 宜昌市| 买车| 和田县| 巴塘县| 五大连池市| 长寿区| 霸州市| 凌云县| 肇源县| 泸州市| 疏勒县| 福清市| 西林县| 南涧| 通榆县| 泗阳县| 横峰县| 卢氏县| 浦北县| 吉隆县| 越西县| 防城港市| 瑞丽市| 璧山县| 定南县| 浙江省| 高台县| 深水埗区| 纳雍县| 宜黄县| 博湖县| 涟源市| 报价| 措勤县| 五原县| 麻城市| 土默特左旗| 河池市| 湟源县|