Сложность (вычисление большой O)

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

У вас есть массив длины n-1, содержащий связанные списки, содержащие списки слов. Каждый связанный список сначала сортируется и затем использует первое слово в связанном списке, массив быстро сортируется. Какова большая сложность этого алгоритма?

Я уже знаю, что:

обходе связанный список О (п) вставки сортировки O (N^2) Быстрая сортировка является (NlogN)

Я просто не знаю, как идти о расчете сложности всего алгоритма

источник

2012-02-17 user1217222

Таким образом, для вставки в список n^2 требуется n^2, а затем nlg (n), и вы собираетесь делать это n-1 раз (правильно?) Итак: я бы сказал, что это (n-1) * (n^2 + n * lg (n)) = ~ n^3 + n^2 * lg (n), поэтому большой O (n^3)? – macduff

Ваш вопрос подразумевает, что массив имеет размер n-1, и все связанные списки имеют размер n. Это верно? – hatchet

«каждый связный список является первой вставки отсортирован»

Это делает для сложности O(n) * O(m^2) или O(n*m^2) - мы должны использовать другое письмо, потому что длина каждого списка не связана с количеством списков.

"то массив quicksorted"

Это добавляет O(n log n).

Итого: O(n*m^2 + n log n), который simpifies к O(n*m^2) (в n log n не имеет существенного значения по сравнению с n*m^2).

источник

2012-02-17 22:01:19

Я не специалист по обозначениям большого О, так что не слишком сильно на меня, если я ошибаюсь: p –

С технической точки зрения, вы должны иметь O (max (nm^2, nlogn)). Опять же, Quicksort O (n^2) в худшем случае, поэтому, если это не анализ в среднем случае, было бы более технически правильно отвечать O (max (nm^2, n^2)). Просто говорю. Вам нужен алгоритм O (nlogn) в худшем случае, попробуйте слить или купировать сортировку. – Patrick87

Сложность (вычисление большой O)

ответ

Смежные вопросы