Здравствуйте, я бы хотел спросить почему вы сказали на Задачи А, решения время сложности алгоритма O(n), если еще есть сортировка которая занимает O(nlogn). я еще новичек в олимпиадном программирование
Добрый день. Да, действительно, сортировка занимает O(nlogn) и второе решение в целом следует оценивать по этой планке. Просто в объяснении сортировка рассматривалась как подготовительная операция, а далее уже сравнивались алгоритмы работы с уже упорядоченной последовательностью: перебор за O(n^2) и два указателя за O(n). Так что вы правы: второе решение в целом работает за O(nlogn), сортировка там самая длительная операция.
Спасибо большое за видео. Если кто-то хочет разобраться в анализе сложности алгоритмов, то почитайте Кормен "Алгоритмы построение и анализ"
Здравствуйте, я бы хотел спросить почему вы сказали на Задачи А, решения время сложности алгоритма O(n), если еще есть сортировка которая занимает O(nlogn). я еще новичек в олимпиадном программирование
Добрый день. Да, действительно, сортировка занимает O(nlogn) и второе решение в целом следует оценивать по этой планке. Просто в объяснении сортировка рассматривалась как подготовительная операция, а далее уже сравнивались алгоритмы работы с уже упорядоченной последовательностью: перебор за O(n^2) и два указателя за O(n).
Так что вы правы: второе решение в целом работает за O(nlogn), сортировка там самая длительная операция.
@@binom-education Спасибо за ответ, желаю вам удачи с этой рубликой