На этот раз сложность O (nlogn) с использованием HeapSort - PullRequest
Новая
       30

На этот раз сложность O (nlogn) с использованием HeapSort

0 голосов
/ 05 марта 2020

Это во времени сложность O (nlogn) времени? Если нет, то как мне исправить это

Цель: использование HeapSort должно найти пары сумм, используя 1 число в каждом массиве, чтобы найти + b = c (задано)

Basi c Функция сортировки HeapSort 

boolean SumPairs(int[] Arr1, int[] Arr2, int p) {

    heapSort(Arr2, p);

    int target = 0;

    for (int i = 0; i < Arr1.length; i++) {
        target = p - Arr1[i];
    if (BinarySearch(Arr2, target) != -1)
        return true;
  }
    return false;
 }

1 Ответ

1 голос
/ 05 марта 2020

Средняя сложность времени правильно реализованной сортировки кучи составляет O (NlogN); см https://en.wikipedia.org/wiki/Heapsort.

Средняя сложность времени правильно реализованного двоичного поиска составляет O (logN); см. https://en.wikipedia.org/wiki/Binary_search_algorithm

Итак, при условии, что методы, которые вы вызываете, правильно реализованы , средняя сложность времени ваших методов составляет O(NlogN) + (O(N) * O(logN)) на вызов. Это уменьшает до O(NlogN).

Обратите внимание, что на самом деле это метод с двумя параметрами массива, поэтому, строго говоря, класс сложности: O(NlogN + MlogN), где M - это длина первого массив и N - длина второго.

...