TimeComplexity из следующих слияния к связные списки

Question

http://www.geeksforgeeks.org/merge-k-sorted-linked-lists/

Со ссылкой на ссылку: Как разделяй и властвуй стратегия дает O (п Log к) сложности, пожалуйста, объясните. Кроме того, я кодировал то же самое несколько иначе. Единственное различие заключается в схеме слияния. Я объединяю первый 2 связанный результат, а затем их результат с другим связанным списком.

Какова будет сложность этого?

Node * mergek(){ 
    int n; 
    puts("Enter number of linked list you want to enter"); 
    scanf("%d",&n); 
    Node ** arr=malloc(sizeof(Node *)*n); 
    int i=0; 
    for(i=0;i<n;i++){ 
     arr[i] = takeInput(); 
    } 
    for(i=0;i<n;i++){ 
     print(arr[i]); 
    } 
    Node * temp=NULL; 
    for(i=0;i<n;i++){ 
     if(i==0){ 
      temp=merge(arr[i],arr[i+1]); 
      i=i+1; 
     } 
     else{ 
      temp=merge(arr[i],temp); 
     } 
    } 
    return temp;  
} 

Я хотел бы знать, если это будет иметь ту же сложность или нет, я е. O (nklog (k)).

Количество слияний остается неизменным.

Answer 1

Хотя количество слияний остается неизменным, структура слияния на самом деле делает сложность времени намного хуже. Предполагая, что у вас есть функция merge() до merge two sorted linked lists в O(n + m) времени (где n = размер первого списка, m = размер второго) и O(1), рассмотрите следующий анализ, в котором я предполагаю, что в каждом списке есть в среднем n элементов.

• Первое слияние будет O(n + n), так как мы слияние два n -sized списки
• Второго слияние будет O(2n + n), так как мы сливаясь один n -sized списка с нашим теперь 2n -sized списка
• Третье слияние будет O(3n + n) ... и так далее.

На данный момент мы должны сложить все дополнения внутри Big-Oh, чтобы получить:

O(2n + 3n + 4n + 5n + ... + kn) 

Сумма всех этих n терминов существенно n*(k(k+1))/2, потому что (k(k+1))/2 является суммой из первые k номера. Принимая постоянные множители и члены младшего порядка из (k(k+1))/2, мы можем видеть, что O((k(k+1))/2) = O(k^2), тем самым предоставляя алгоритм сложности O(n*k^2).

Я написал небольшую статью по этой проблеме и проанализировал дальше, степень различий в сложности. Вы должны проверить его here

---

Чтобы ответить на другой вопрос о том, как делает разделяй и властвуй подход на самом деле выход O (пк * журнал (K)), подумайте о том, как сортировка слиянием работает.

Если у нас есть $ n $ items, merge sort делает n количество работы, столько раз, сколько требуется для суммирования n элементов вместе, прежде чем они станут одним целым списком. Это число log(n) (база базы 2 из n), поэтому требуется ряд шагов пропорционально nlog(n) (опять же, осознаем, что делаем n количество работ, потому что всегда есть n элементов в игре, log(n) раз).Причина сортировки слияния должна разбивать список на отдельные элементы до их слияния, потому что одна единица - это самая маленькая вещь, которую мы можем получить по определению, отсортированную, без какой-либо работы по ее сортировке.

В нашем случае каждый список уже отсортирован, поэтому мы можем рассматривать каждый из списков k (размером ~ n) как элемент, отсортированный по определению. Нет необходимости разбивать отсортированный список вниз. Так как есть k списков с элементами n, всегда будет n*k элементов в игре. К счастью, поскольку каждый список уже отсортирован, нам нужно объединить только k «элементы», а не все элементы списка n*k. Таким образом, та же логика преобладает, поскольку мы должны объединить k элементов/списков вместе. Поскольку каждый список принимает O(n) время для слияния, в отличие от O(1) при работе с n*k отдельных элементов, это занимает время пропорционально O(nk*log(k)).