發問區
會員登入
新使用者？立即註冊
.
服務首頁|服務說明|Yahoo!奇摩.知識+ 首頁
知識分類
電腦網路
科學常識
醫療保健
煩惱心事
生活資訊
手機通訊
休閒嗜好
視聽娛樂
運動體育
社會人文
商業金融
教育學習 .如何做
煩惱
主題知識
.我要發問 發表 我要發問 ..熱門： 瘦大腿 除口臭 天穿日 濃茶少喝 臉型看個性 主題 金蛇報喜，大過好年 用手機上知識+ .知識搜尋 ....知識+ 首頁> 電腦網路> 程式設計> Java 加入追蹤 轉寄朋友 友善列印 .知識問題|
binary search 複雜度. 發問者： 我還記得 我們的約定 ( 初學者 4 級)
發問時間： 2008-10-22 03:04:44
解決時間： 2008-10-24 08:40:19
解答贈點： 5 ( 共有 0 人贊助 )
回答： 1 評論： 0 意見： 1
[ 檢舉 ]
網友正面評價
100%
.共有 4 人評價.binary search 的時間複雜度
最差是O(logn)??
要怎麼證明呢 可否從程式碼證出? 2008-10-22 03:09:11 補充
假如我有10個數字 0 1 2 3 4 5 6 7 8 9
這樣最差的情況是要找幾次呢? 3次?4次?
最佳解答發問者自選
.. 回答者： Leslie ( 專家 3 級 )
擅長領域： 古典樂 | 英文
回答時間： 2008-10-22 12:42:19
[ 檢舉 ] .
Binary Search 的
worst case (O(log n)) 比較簡單分析, 通常是用直觀的:
Worst case 是因為原來 n 個數中要找 q, 比一次 (q 和位置在中間的數比) 後,
變成 n/2 個數 (其實是 (n-1)/2) 中要找 q, 再比一次, 變成 n/4 個數中要找 q,
..., 一直到剩 1 個數或沒有數中要找 q (至此才找到或沒找到).
這樣子的從 n 開始, 每次變一半, 到 最後的 1, 要經過 log n 次 (底為 2).
因次共比了 log n 次 (譬如說 n 為 1000, log n 約為 10)
也可如下證明:
設 T(n) 是 worst case 須要的比較次數, 表示成 recurrence relation:
T(n) = T(n/2)+1 for n >=2, 及
T(1) = 1
這可解出 T(n) = O(log n)
( T(n) = T(n/2)+1
= T(n/4)+1+1 = ...
= T(1)+1+1+...+1
= 1+logn
)
或是, 請看另一證明 (用二分搜尋樹):
http://tw.myblog.yahoo.com/jw!F3tBV.meGR8SV8Wg76cKjOVVDA--/article?mid=36
參考資料
DS & Algorithm textbooks 2008-10-23 15:23:24 補充
> 可否從程式碼證出?
學演算法分析, 是沒有人直接由程式碼看的,
時間複雜度是沒寫出程式前, 由方法就要分析出的.
> 3 次或 4次?
答案是如某位高手在意見欄說的.
只是, 不同的人寫出的 binary search 程式, 3 或 4 都是有可能的.
重點是, log n 次和 (log n)+1 次有差嗎? 反正是 O(log n).
2008-10-23 15:23:29 補充
> 可否從程式碼證出?
學演算法分析, 是沒有人直接由程式碼看的,
時間複雜度是沒寫出程式前, 由方法就要分析出的.
> 3 次或 4次?
答案是如某位高手在意見欄說的.
只是, 不同的人寫出的 binary search 程式, 3 或 4 都是有可能的.
重點是, log n 次和 (log n)+1 次有差嗎? 反正是 O(log n).
相關詞：
時間複雜度,空間複雜度,複雜度 定義,複雜度計算,演算法 複雜度,時間複雜度比較,複雜度 英文,資料結構時間複雜度,複雜度分析,密碼複雜度
複雜度,binary search,時間複雜度,logn,程式碼,worst,log,證明,分析,位置[ 快速連結 ] 其它回答( 0 ) | 意見( 1 ) | 評論( 0 )
.發問者評價 了解~! .發表你的評價
你的評價 發表評價： 正面 普通 負面
評價內容： 發表 取消
.
加入追蹤 轉寄朋友 友善列印 .馬上按讚 加入 Yahoo! 奇摩 知識+ 粉絲團
•桂綸鎂從早到晚陪著你
•首度曝光!!桂綸鎂私生活
•超萌尺度!自然眼照大公開
•免費下載空姐英文教戰手冊
•多益700分線上測驗題庫
•解析奧斯卡電影背後的秘密
相關問答
[ C&C++ ]時間複雜度問題 感謝了!!
.
[ C&C++ ]時間複雜度
.
[ C&C++ ]時間複雜度:asymptotic growth rate
.
[ 其他 ]有關時間複雜度
.
[ 商業 ]演算法複雜度的問題[初考考題]
.
[ Java ]時間複雜度該怎麼計算?
.
更多
.其他回答(0)
意見(1)
相關評論(0)
.目前沒有資料
001 意見者： 鴨子 ( 研究生 1 級 )
擅長領域： VisualBasic | Java
發表時間： 2008-10-22 09:00:11
[ 檢舉 ] ..4次 1 發表意見發表意見字數已達上限，要改成發表評論嗎？. 發表 取消 .
目前沒有資料 我要評論 最新Java
發問中
已解決
.Java三角形的題型
當個創世神無法開啟
更多
更多 註冊
會員登入 .公告： 知識團員轉粉絲全數完成 .
HOT! 拍賣 | 雙核心 四核心 奇美19吋 .
.刊登贊助網站•全民免費學電腦 8大熱門職訓課
www.pccenter.com.tw
優惠僅到月底！學承職訓電腦課程免費學，快速提升職場競爭力，立即搶先申請！
www.pccenter.com.tw
•領取學承新年免費iPad好禮
www.pccenter.com.tw
新年雙好禮！填表先送線上課程，報名電腦專案再送免費iPad4，只到3/31！
www.pccenter.com.tw
•學電腦不用錢！政府補助至高全額
www.pcschool.com.tw
真正的政府補助課程，3月份電腦技能培訓班，正式開放預約報名，名額有限請把握！
www.pcschool.com.tw
•國際3Ds MAX學電腦
www.cadtc.com.tw
二個月密集完成動畫夢想，不需基礎也可完成120秒以上作品，擁有動畫製作實力！
www.cadtc.com.tw
•雙喜超高價到府回收電腦零組件
s0937s1255.0913257527.com.tw
台南高雄回收電腦可報價比較，學校、個工報廢主機340元起，當天來電當天服務！
s0937s1255.0913257527.com.tw
•Yahoo！奇摩搜便利
tw.emarketing.yahoo.com
萬筆店家資料一次到位，搜樂子、找服務隨你挑
tw.emarketing.yahoo.com.
精選關鍵字
..錯誤 除錯 運算式 亂碼 星星 註解 文字 執行緒 程式語言 排序 編譯 陣列 語法 mysql 宣告 script 執行 迴圈 題目 物件 組譯 解釋 圖形化 視窗 程式碼 SQL 動態
.知識搜尋 ...雅虎資訊 版權所有 (c) 2013 Yahoo! Taiwan. All Rights Reserved. 「本服務設有管理員」
服務條款隱私權政策..知識+ 之問答內容是由參與Yahoo!奇摩知識+ 之網友提供，僅供參考，Yahoo!奇摩不保證其正確性。
...
.
|
phibrainno1 發表在 痞客邦 留言(0) 人氣()
留言列表
留言列表
