Может кто-нибудь объяснить мне, как эта программа имеет эффективность N2LogN? Я думаю, что это должно быть N2 - PullRequest
Новая
       6

Может кто-нибудь объяснить мне, как эта программа имеет эффективность N2LogN? Я думаю, что это должно быть N2

0 голосов
/ 28 июня 2018 
class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        from fractions import Fraction
        ans = float('inf')

        N = len(quality)
        for captain in xrange(N):
            # Must pay at least wage[captain] / quality[captain] per qual
            factor = Fraction(wage[captain], quality[captain])
            prices = []
            for worker in xrange(N):
                price = factor * quality[worker]
                if price < wage[worker]: continue
                prices.append(price)

            if len(prices) < K: continue
            prices.sort()
            ans = min(ans, sum(prices[:K]))

        return float(ans)

Поправь меня, если я ошибаюсь. По мне, O (n) = N (N + logN) = N2 + NLogN >> = N2 N для внешней петли N для внутреннего цикла логН для сортировки

ссылка на программу

1 Ответ

0 голосов
/ 28 июня 2018

Поправь меня, если я ошибаюсь. По моему мнению, O (n) = N (N + logN) = N2 + NLogN >> = N2 N для внешнего цикла N для внутреннего цикла logN для сортировки

Ошибка - последняя часть. Сортировка занимает N log N раз, а не log N.

А если подумать, как сортировка может занять меньше, чем линейное время? Вы, очевидно, должны проверять каждое значение хотя бы один раз, верно?

Итак, общее время составляет N (N + N log N), что составляет O(N^2 log N).

...