Самый эффективный способ найти все комбинации n выбрать 2

Question

Самый эффективный способ найти все комбинации n choose 2 для 2 <= n <= 100000?

Например, 5 choose 2 является

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

Это то, что я до сих пор для тестирования худшего случая:

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

ВЫВОДА

Time taken 28 seconds 799 milliseconds 
Pairs = 4999950000 

Я могу ошибаться, но время сложность O (n^2).

Есть ли более эффективный алгоритм для обработки наихудшего случая?

Answer 1

Нет «наилучшего случая» или «наихудшего случая». Вам нужно сгенерировать точно пары (n * (n - 1))/2, и ваша текущая программа генерирует именно эти пары и ничего больше. Таким образом, ваша программа является оптимальной (в смысле алгоритмического анализа) и равна θ(n^2).

Некоторые оптимизации могут быть возможны с использованием различных трюков (например, побитовые операции для перехода от одной пары к следующей, генерирования пар массивов в одной итерации, оптимизации компилятора и т. Д.), Но ни один из них не повлияет на временную сложность алгоритма.

Answer 2

Посмотрите на это так, что, если «n» было числом пар, а не оригинальным размером выбранного массива. Сложность вашего подхода - O (n), а не O (n^2). Обратите внимание, что вы заполняете один индекс массива для каждой итерации внутреннего цикла независимо от вашего цикла outter.

Учитывая, что я не думаю, что вы можете сделать значительно лучше. Это будет нижней границей, вы не можете создать две пары на шаг! Там, я думаю, это оптимальное решение.

Для продолжения - если выход n^2 - размер ввода, то ваша нижняя граница всегда n^2, если вы должны касаться каждой точки данных один раз. Что ты здесь делаешь.