n의 모든 조합을 찾는 가장 효율적인 방법 2

Question

2 <= n <= 100000에 대한 n choose 2의 모든 조합을 찾는 가장 효율적인 방법은 무엇입니까? 내가 잘못하지만 시간이 될 수

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define MAX_ITEMS 100000 

void combinations(int[], int); 

long long count = 0; 

int main(void) { 
    int *arr = (int*) calloc(MAX_ITEMS, sizeof(int)); 
    if (!arr) { 
     printf("Error allocating memory."); 
     exit(1); 
    } 

    int i, n = MAX_ITEMS; 

    for (i = 0; i < MAX_ITEMS; i++) { 
     arr[i] = i + 1; 
    } 

    clock_t start, diff; 
    int msec; 

    start = clock(); 
    combinations(arr, n); 
    diff = clock() - start; 

    msec = diff * 1000/CLOCKS_PER_SEC; 
    printf("\n\nTime taken %d seconds %d milliseconds", msec/1000, msec % 1000); 
    printf("\n\nPairs = %lld\n", count); 

    return 0; 
} 

void combinations(int arr[], int n) { 
    int i, j, comb1, comb2, end = n - 1; 

    for (i = 0; i < end; i++) { 
     for (j = i + 1; j < n; j++) { 
      // simulate doing something with data at these indices 
      comb1 = arr[i]; 
      comb2 = arr[j]; 
      // printf("%d %d\n", arr[i], arr[j]); 
      count++; 
     } 
    } 
} 

OUTPUT

Time taken 28 seconds 799 milliseconds 
Pairs = 4999950000 

: 예를 들어

는 5 choose 2이 내가 지금까지 최악의 경우를 테스트하기 위해이 무엇

1 2 
1 3 
1 4 
1 5 
2 3 
2 4 
2 5 
3 4 
3 5 
4 5 

입니다 복잡성은 O (n^2)입니다.

최악의 경우를 처리하는보다 효율적인 알고리즘이 있습니까?

Answer 1

"최상의 사례"또는 "최악의 사례"가 없습니다. 정확히 (n * (n - 1))/2 쌍을 생성해야하며, 현재 프로그램은 정확히 쌍을 생성하고 그 밖의 것은 생성하지 않습니다. 따라서 귀하의 프로그램은 (알고리즘 분석의 관점에서) 최적이고 θ(n^2)입니다.

다양한 트릭 (예 : 한 쌍에서 다음 쌍으로 이동하는 비트 연산, 한 번의 반복으로 대량 쌍 생성, 컴파일러 최적화 등)을 사용하여 일부 최적화가 가능할 수 있지만 알고리즘의 시간 복잡성에는 영향을주지 않습니다.

Answer 2

"n"이 배열의 원래 크기가 아닌 쌍의 수인 경우이 방법을보십시오. 접근법의 복잡성은 O (n)이 아니라 O (n^2)입니다. 아웃터 루프에 관계없이 내부 루프의 각 반복에 대해 배열의 인덱스 하나를 채 웁니다.

감안할 때, 당신이 훨씬 더 잘할 수 있다고 생각하지 않습니다. 이것은 하한이 될 것이고, 한 걸음마다 두 쌍을 생산할 수 없습니다 !! 내가 최적의 솔루션이라고 생각할 것입니다.

계속 진행 - 출력이 n^2 인 경우 모든 데이터 포인트를 한 번 터치해야한다는 가정하에 하한값은 항상 n^2입니다. 당신이 여기 있습니다.