запрос алгоритма

Question

Если мы знаем ниже, связанный с временной сложностью проблемы Ω(n^2), правильно ли я считаю, что невозможно иметь алгоритм с наихудшей временной сложностью O(n log n)?

Answer 1

Если нижняя граница временной сложности задачи Ω(n^2), то это означает, что алгоритм решения этой задачи должен принять по крайней мереC*n^2 времени.

С другой стороны, у вас есть алгоритм, который принимает не болееK*n*logn время.

Этот алгоритм не может работать больше, чем nlogn. Вам нужен алгоритм, который работает как минимум n^2 времени.

Поэтому; этот алгоритм не может решить эту проблему. Ты прав.