Задачі
Тато у Васі сильний...
Чи можна дізнатись чому розв'язок за n*log(n), тобто близько 10 мільйонів операцій не вкладається в 3 секунди, хоча деякі мої розв'язки з 125 мільйонами вкладались в 3 секунди?І чому один і той сами розв'язок при декількох здачах видає різний середній час виконання?
awpris відповів:
Бо Ваш розв'язок має складність не n*log(n)... :)
Там лише quicksort чи heapsort(два розв'язки), а як відомо в них складність n*log(n). Там ше є три проходи за n. Два сортування. Тобто загалом 2*nlog(n)+3n. Мало б вкладатись..
awpris відповів:
Як бачите - припущення (що "мало б") не вірне. :)
Ищите решение за O(n). Гарантирую, что оно есть.
Почитайте про хэш-таблицы те, кому интересно как решать за O(n)
Или про цифровую сортировку - немного дольше, но в тайм лимит укладывается.