降低時間複雜度

int main() 
{ 
    int n ; 
    std::cin >> n; // or scanf ("%d", &n); 
    int temp; 
    if(n ==1) temp = 1; // if n is 1 number is power of 2 so temp = 1 
    if(n % 2 != 0 && n!= 1) temp =0; // if n is odd it can't be power of two 
    else 
    { 
     for (;n && n%2 == 0; n /= 2); 
     if(n > 0 && n!= 1) temp = 0; // if the loop breaks out because of the second condition 
     else temp = 1; 
    } 

    std::cout << temp; // or printf ("%d", temp); 
}

上面的代碼檢查一個數是否是2的冪。最壞的運行時複雜度是O（n）。如何通過降低時間複雜性來優化代碼？降低時間複雜度

來源

2011-01-25 AlgorithmGeek

你的代碼的運行時的複雜性在最壞的情況是O（log n）的你仍然可以做的更好（O（1））爲如下所示 – CashCow 2011-01-25 10:12:53

嘗試if(n && (n & (n-1)) == 0) temp = 1;檢查數字是否爲2的冪。

例如：

n = 16;

1 0 0 0 0 (n) 
& 0 1 1 1 1 (n - 1) 
    _________ 
    0 0 0 0 0 (yes)

2的一個數字只有一個比特集。

n & (n - 1)unsets the rightmost set bit。

運行時間O(1) ;-)

由於@GMan注意到n需求是一個無符號整數。負符號整數的按位運算是實現定義的。

來源

2011-01-25 09:57:30

可愛的小圖。當然，`n`需要是`unsigned`來保證這個工作。 – GManNickG 2011-01-25 10:03:59

這個怎麼樣？

bool IsPowerOfTwo(int value) 
{ 
    return (value && ((value & (value-1)) == 0); 
}

來源

2011-01-25 09:58:21 EboMike

試試這個：bool isPowerOfTwo = n && !(n & (n - 1));

來源

2011-01-25 09:59:36 Botz3000

而不是分割數2，你可以通過右轉向1.它這是2,4,8,16,32除法的普遍優化規則和等等。這種劃分可以由右移1,2,3,4,5等替代。它們在數學上相當。

移位更好，因爲彙編器分割指令在大多數CPU架構上效率非常低。邏輯右移指令的執行速度要快得多。

但是，編譯器應該能夠爲你做這個優化，或者它有一個非常糟糕的優化器。從風格上看，在C代碼中編寫除法和模運算符可能會更好，但要驗證編譯器是否實際優化了它們以轉移操作。

來源

2011-01-25 11:05:13 Lundin

bool ifpower(int n) 
{ 
    if(log2(n)==ceil(log2(n))) return true; 
    else return false; 
}

來源

2014-10-16 06:29:35 rajeev

降低時間複雜度

回答

相關問題