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)です。

さまざまなトリック（ビット単位の操作（ある対から次への移動、1回の反復でのバルクペアの生成、コンパイラの最適化など）では可能ですが、どれもアルゴリズムの時間の複雑さに影響しません。

Answer 2

このように見てみましょう。「n」が選択された配列の元のサイズではないペアの数であればどうでしょうか。あなたのアプローチの複雑さは、O（n）ではなくO（n^2）です。アウトターループにかかわらず、内側ループの各繰り返しに対して、配列の1つのインデックスを入力することに注意してください。

これを考えると、私はあなたがはるかに優れていると思います。これは下限になるでしょう。ステップごとに2つのペアを生成することはできません！私はこれが最適な解決策だと思うでしょう。

続行する - 出力がn^2の場合、すべてのデータポイントを1回タッチする必要があると仮定して、入力のサイズは常に下限です。あなたはここにいます。