為何二分查詢的最壞情況的步數是lgn而不是log(2)n?

時間 2021-05-30 03:16:03

1樓:

因為lg(n)/log2(n) = log2(10) = 常數,時間複雜度是忽略係數的。所以可以用任意底數表達對數複雜度。

2樓:

1.演算法分析中寫的lg的底數預設為2

2.由於換底公式的存在,底數的變化實際上只會引起常數因子變化,在用漸進符號時常數因子不影響分析結果。

3樓:健步俠阿杜

因為我們計算程式執行時間一般預設是使用大O符號,大Ω符號,大Θ符號(中文翻譯好山寨的感覺),(定義見這裡大O符號),對於這三符號,對步數的定義都是可以乘除乙個常數C的。

而對於log符號,各種地書的區別就是差乙個係數,所以是不是非要寫log2 N還是logN(以10為底)都沒有本質區別

4樓:趙扶風

T=K*log2(N) 注:2是小2

時間T與以2為底的對數成正比。實際上,由於所有的對數都和其他對數成比例(從底數為2轉換到底數為10需乘以3.322),我們可以將這個為常數的底數也併入K.由此不必指定底數:

如何看待事實與價值二分的問題?

普特南當然是錯誤的。第一,古典的不足,在於找不到從事實中推論出價值的路徑。第二,普特南的錯誤,在於他說不清價值怎麼來的,然後亂說了一通。整個世界是事實,這是一種客觀視角。所謂價值,需要一套評判標準。標準何來,決定了整個倫理學的方向。 已登出 就普特南本人而言他對事實和價值二分法的看法主要有兩個層面吧...

為什麼音符的節拍是全音符二分音符四分音符 而不是全音符三分音符九分音符二十七分音符 ?

王康卜 音符的拍數是把乙個音符分成多少份,音符的數量越多時值就越短,比如乙個全音符的時值是四,那麼所有的全音符都是四,可以把乙個全音符變成四個相同時值的四分音符每個音符的時值就是一,但是這個名稱問題真的不用特別較真兒,就只是需要你按照科學規範的名稱背過了就可以了。音符時值這個東西沒有數位化的概念,只...

如果分析的例子中,自變數和因變數都是二分類變數,該做什麼分析?

暮雪寒泉 對於題主的問題,個人認為適合用離散選擇模型進行分析,由於因變數的是對一種事務的程度,既即可以將因變數理解為有序變數,即適合用有序logit或有序probit模型進行分析。在stata中,如要分析自變數互動對因變數的,就可以直接將兩個變數相乘作為乙個新變數。 瓔珞 兩列變數都不是連續,做相關...