薩姆的所有對

Question

問題語句間位的差異如下：

給定n個整數的整數數組，找到的位差之和中，可以從陣列元件形成的所有對。一對（x，y）的位差是在x和y的二進制表示中相同位置處的不同位的計數。例如，2和7的位差是2. 2的二進制表示是010並且7是111（第一位和最後一位在兩個數字上不同）。

實例：

Input: arr[] = {1, 2} 
Output: 4 
All pairs in array are (1, 1), (1, 2) 
         (2, 1), (2, 2) 
Sum of bit differences = 0 + 2 + 
         2 + 0 
         = 4 

基於this post最有效的解決方案（運行的O（n）的時間）如下：

的想法是計數在單獨比特位置的差異。我們從0到31進行遍歷，並對第i個位進行計數。讓這個計數是'計數'。將有「n計數」數字與我沒有設置。所以第i位的差異數將是「count *（n-count）* 2」。

// C++ program to compute sum of pairwise bit differences 
#include <bits/stdc++.h> 
using namespace std; 

int sumBitDifferences(int arr[], int n) 
{ 
    int ans = 0; // Initialize result 

    // traverse over all bits 
    for (int i = 0; i < 32; i++) 
    { 
     // count number of elements with i'th bit set 
     int count = 0; 
     for (int j = 0; j < n; j++) 
      if ((arr[j] & (1 << i))) 
       count++; 

     // Add "count * (n - count) * 2" to the answer 
     ans += (count * (n - count) * 2); 
    } 

    return ans; 
} 

// Driver prorgram 
int main() 
{ 
    int arr[] = {1, 3, 5}; 
    int n = sizeof arr/sizeof arr[0]; 
    cout << sumBitDifferences(arr, n) << endl; 
    return 0; 
} 

什麼我不完全清楚是怎麼當有兩個for循環1每次迭代遞增的運行時間將是線性的。我解釋它的方式是由於外循環從0到32 （對應於每個數字的第0和第32位）迭代，並且因爲我猜測所有的32位移位都會在相同的時鐘週期內發生（或者與線性迭代相比相對較快），則總體運行時間將由陣列上的線性迭代支配。

這是正確的解釋嗎？

Answer 1

在英語中，「我的算法在O（n）時間運行」轉換爲「我的算法運行時間與最大輸入成正比，爲n」。這個比例方面的原因是在外部循環中的32次迭代沒有任何區別。執行時間仍然與n成正比。

讓我們看看一個不同的例子：

for (int i=0; i<n; i++) { 
    for (int j=0; j<n; j++) { 
     // do something 
    } 
} 

在該示例中，執行時間是與n成比例所以它不爲O（n）。然而，它是O（n ）。並且在技術上也是O（也可以是O）和O（也可以是）......。這從定義出發。

只有很多你可以用英語來談論這個東西而不會有誤解，所以如果你想確定最好的概念，你可以在介紹算法教科書或在線課程中查看正式的定義，幾個例子。