arrays - 所有对之间的位差之和

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) 的运行时间)解决方案如下:

The idea is to count differences at individual bit positions. We traverse from 0 to 31 and count numbers with i’th bit set. Let this count be ‘count’. There would be “n-count” numbers with i’th bit not set. So count of differences at i’th bit would be “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

在英语中，“My algorithm runs in O(n) time”翻译为“对于非常大的输入，我的算法运行时间最多与 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(n³) 和 O(n⁴)，...也是如此。这是根据定义得出的。

你只能用英语谈论这些东西而不会被误解，所以如果你想确定这些概念，你最好查看介绍性算法教科书或在线类(class)中的正式定义，并制定一些示例。