改进嵌套循环的优化

问题描述：

我正在制作一个简单的程序来计算数组中可以被3个数组长度整除并且用户确定值的对数。改进嵌套循环的优化

现在我的代码非常好。但是，我只想检查是否有更快的计算方法，从而减少编译时间？

由于数组的长度为10^4或更少，编译器需要少于100ms。但是，当它达到10^5时，它会达到1000毫秒，那为什么呢？以及如何提高速度？

#include <iostream> 

using namespace std; 

int main() 
{ 
    int N, i, b; 
    b = 0; 
    cin >> N; 

    unsigned int j = 0; 
    std::vector<unsigned int> a(N); 
    for (j = 0; j < N; j++) { 
     cin >> a[j]; 
     if (j == 0) { 
     } 

     else { 
      for (i = j - 1; i >= 0; i = i - 1) { 
       if ((a[j] + a[i]) % 3 == 0) { 
        b++; 
       } 
      } 
     } 
    } 

    cout << b; 

    return 0; 
}

如果您的代码正常工作，并且只想改进它，请考虑询问[codereview.stackexchange.com]（https://codereview.stackexchange.com/）。 –

附注。如果你优化你的代码，你可能会提高'执行时间'。编译时间通常不是一个因素，因为这只有在您构建程序时才会发生一次:) –

https://*.com/questions/1887097/why-arent-variable-length-arrays-part-of-the -c-标准 – Tyger

答

您的算法具有O(N^2)复杂性。有一个更快的方法。

(a[i] + a[j]) % 3 == ((a[i] % 3) + (a[j] % 3)) % 3

因此，你不需要知道确切的数字，你只需要知道它们的余数除以三。总和的零余数可以用两个数字以零余数(0 + 0)和两个数字以及余数1和2(1 + 2)接收。

结果将等于r[1]*r[2] + r[0]*(r[0]-1)/2其中r[i]是数字的数量，其余数等于i。

int r[3] = {}; 
for (int i : a) { 
    r[i % 3]++; 
} 
std::cout << r[1]*r[2] + (r[0]*(r[0]-1))/2;

该算法的复杂度为O(N)。

答

我以前遇到过这个问题，虽然我没有找到我的特定解决方案，但可以通过哈希来提高运行时间。

的代码会是这个样子：

// A C++ program to check if arr[0..n-1] can be divided 
// in pairs such that every pair is divisible by k. 
#include <bits/stdc++.h> 
using namespace std; 

// Returns true if arr[0..n-1] can be divided into pairs 
// with sum divisible by k. 
bool canPairs(int arr[], int n, int k) 
{ 
    // An odd length array cannot be divided into pairs 
    if (n & 1) 
     return false; 

    // Create a frequency array to count occurrences 
    // of all remainders when divided by k. 
    map<int, int> freq; 

    // Count occurrences of all remainders 
    for (int i = 0; i < n; i++) 
     freq[arr[i] % k]++; 

    // Traverse input array and use freq[] to decide 
    // if given array can be divided in pairs 
    for (int i = 0; i < n; i++) 
    { 
     // Remainder of current element 
     int rem = arr[i] % k; 

     // If remainder with current element divides 
     // k into two halves. 
     if (2*rem == k) 
     { 
      // Then there must be even occurrences of 
      // such remainder 
      if (freq[rem] % 2 != 0) 
       return false; 
     } 

     // If remainder is 0, then there must be two 
     // elements with 0 remainder 
     else if (rem == 0) 
     { 
      if (freq[rem] & 1)   
       return false; 
     }   

     // Else number of occurrences of remainder 
     // must be equal to number of occurrences of 
     // k - remainder 
     else if (freq[rem] != freq[k - rem]) 
      return false; 
    } 
    return true; 
} 

/* Driver program to test above function */ 
int main() 
{ 
    int arr[] = {92, 75, 65, 48, 45, 35}; 
    int k = 10; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    canPairs(arr, n, k)? cout << "True": cout << "False"; 
    return 0; 
}

，对于AK的工作（在你的案件3）但话又说回来，这是不是我的代码，但是代码可以在following link.找到并有适当的解释。我不只是粘贴链接，因为我认为这是不好的做法。

改进嵌套循环的优化

相关推荐