중첩 루프의 최적화 개선

Question

배열의 3 쌍의 길이로 나눌 수있는 쌍의 수를 계산하는 간단한 프로그램을 만들고 값은 사용자가 결정합니다.

이제 내 코드는 완벽합니다. 그러나, 나는 단지 컴파일 시간을 단축시키는 결과를 산출하는 더 빠른 방법이 있는지 확인하고자한다.

배열의 길이가 10^4 이하이므로 컴파일러는 100ms 미만을 소요합니다. 그러나 10^5까지 증가하므로 1000ms까지 올라갑니다. 왜 이렇게됩니까? 그리고 속도를 향상시키는 방법?

#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; 
} 

Answer 1

알고리즘의 복잡도는 O(N^2)입니다. 더 빠른 방법이 있습니다.

(a[i] + a[j]) % 3 == ((a[i] % 3) + (a[j] % 3)) % 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)입니다.

Answer 2

전에이 문제가 발생했습니다. 특정 솔루션을 찾지 못했지만 해싱을 통해 실행 시간을 향상시킬 수 있습니다. AK 작동

// 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; 
} 

(귀하의 경우 3) 하지만 다시이 내 코드가 아니라 코드는 당신이 following link.에서 찾을 수 있습니다

코드는 다음과 같을 것 적절한 설명과 함께. 내가 생각하기에 좋지 않은 링크이기 때문에 붙여 넣기 만하지는 않았다.