這個函數的計算複雜度是多少？

我想知道這個函數的計算複雜度是多少？這個函數的計算複雜度是多少？

2 ^（的log（n）-1）

的日誌基地2

2012-09-04 dgamma3

你已經有了答案。 O（2^logn）時間。這是指數。 – DarthVader

@DarthVader nope。 OP要求本功能的CC。 – 2012-09-04 05:22:15

@DarthVader哦，如果你將一個數字提升到一個以數字本身爲底數的對數，那麼它絕對不是指數的，而是線性的。 – 2012-09-04 05:23:23

這取決於你用什麼計算算法所有的對數和權力。如果你足夠聰明地注意到這個函數基本上是一個2的除法運算，那麼你可以通過做一個右移來在一個固定的時間內（即O(1)）實現整數。

2012-09-04 05:21:39

謝謝你。所以因爲這個數字可以被2整除，這是如何使它O（1） – dgamma3

是的，這是一個奇怪的問題。這有點像問：這個函數的複雜性：Sort（）。 :) – aquinas

@ dgamma3仔細閱讀答案。（並且它不需要被2整除）。 – 2012-09-04 05:26:08

回答