時間複雜度計算時，N * 4 ^ N 可以簡化成4 ^ N 嗎？最後的豌豆2018-03-06 08:06:38

不可以。

Big O的定義是

f(n) \in O (g(n))

if there exists constant

c

，

n_0

such that for all

n > n_0

，

f(n) < c \cdot g(n)

。

很顯然讓

c = (N+1)

，

n_0 =1

似乎可以， 但

c

必須是 constant，所以不行。

時間複雜度計算時，N * 4 ^ N 可以簡化成4 ^ N 嗎？冒泡2018-03-06 10:29:17

判斷f（n）和g（n）的關係的簡單辦法可以計算它倆的比值在n趨向無窮大時候的值

lim（（n+lgn）/n）=lim（1+lgn/n）=1，所以n和n+lgn同階

lim（n*4^n/（4^n））=lim（n）=∞，所以前者高階

時間複雜度計算時，N * 4 ^ N 可以簡化成4 ^ N 嗎？rsa2018-03-07 20:09:24

O（n * 4^n） 不能簡化為 O（4^n）。

假設 f（n），g（n） 恆為正數，f（n） 和 g（n） 同階是指存在正數 a，b（a < b），使得存在一個 N，當 n > N 時恆有 a < f（n）/g（n） < b。

如果 f（n） = n * 4^n，g（n） = 4^n，那麼 f（n）/g（n） = n，對於任意正數 a，b（a < b），取 n = ［b］ + 1，則 f（n）/g（n） > b，不滿足 a < f（n）/g（n） < b。所以 n * 4^n 和 4^n 不同階。

LeetCode 那題的複雜度確實是 O（n * 4^n），因為最壞情況下，加入返回的 vector 的字串總長是 n * 4^n。

有人說輸出不能算在複雜度裡面，這是有點問題的。這題是把所有的字串裝在一個 vector 裡面。如果說 push_back 也不算複雜度的話，恐怕很多演算法都是 O（1） 的了。

感謝 immortalCO 指正。

時間複雜度計算時，N * 4 ^ N 可以簡化成4 ^ N 嗎？w20142018-04-12 20:26:31

不約不約

啊不對是不能約分。

說題目的問題吧。不能隨隨便便約分…指數上的東西哪有等價無窮大替換這說啊…

說題目…

實際上我支援你的看法。

輸出了那麼多個字元就是至少需要同等複雜度的時間…

怎麼最佳化也最佳化不了的…………

裸搜的話…空間O（n）

時間…如果只考慮賦值運算的話他們說的對。如果也考慮輸出的話你說的對。

然而輸出並不快…並不能忽略不計……而且高階無窮大本來就不能忽略…雖然有時有的人會把常數極小的高階項（比如認為邏輯判斷不用時間）忽略，但那從數學上說是極其不嚴謹的…所以我更贊同你的說法。

再吐一槽…

數學上O是向下相容的…也就是說如果他們說的對那麼你說的也一定對…

甚至我說這個是O（n！）問題也不大……

然而計算機老師不可能承認的啊哈哈哈

時間複雜度計算時，N * 4 ^ N 可以簡化成4 ^ N 嗎？知乎使用者2020-03-24 06:38:45

請區分

O(4^n)

和

4^{O(n)}

。另外想達到你的目的的話可以使用

O^*(\cdot)

記號。

The O* notation suppresses polynomial factors in the input size。