У меня есть один алгоритм здесь.
Нажмите здесь, чтобы посмотреть изображение алгоритма
Что он делает, он проходит массив и находит 3 самых больших значения и возвращает их сумму. Например, массив [1,2,3,4,5] вернет 12 (3+4+5=12).
Алгоритм на изображении говорит, что это O (nlogk). Но это то, чего я не могу понять.
Следующее – это моя точка зрения на первый цикл for на изображении:
Метод кучи "insert()" и "deleteMin()", оба они принимают O(logn). Таким образом, в первом цикле for он делает O(2*logn), добавляя время выполнения, которое равно просто O(logn). Поскольку первый цикл for повторяется для всех элементов массива, общее время выполнения первого цикла for равно O(nlogn).
Вот моя точка зрения на второй цикл while на изображении:
Из предыдущего цикла for мы удалили некоторые минимальные значения, если h.size() > k. Таким образом, количество значений в куче в настоящее время равно k. "sum=sum+h.min()" занимает O(logn), потому что поиск минимального значения в куче занимает O(logn), если я правильно знаю, и "h.deleteMin()" также занимает O(logn), потому что он должен искать снова и удалять. То же самое можно сказать и о O(2*logn), добавляя их время выполнения, которое равно просто O(logn). Поскольку мы повторяем этот цикл while только k раз, потому что есть k элементов, поэтому 2-й цикл while приводит к O (k * logn)
Итак, у нас есть O(nlogn) из первого цикла for и O(klogn) из второго цикла while. Очевидно, что O(nlogn) больше, чем O(klogn), так как k — некоторая константа. Таким образом, этот алгоритм заканчивается в O(nlogn) в конце.
Но ответ говорит, что это "O(nlogk)" вместо "O(nlogn)".
Можете ли вы объяснить причину?
