Блог пользователя mezhaka

Первый раз столкнулся с тем, что реализация имеет значение.
Автор mezhaka, 15 лет назад, перевод, По-русски

Моё решение div. 2 B round #92 не прошло по времени. Сейчас я его поправил и оно проходит тесты, но что интересно сложность по-идее у него такая же. Вот если кому интересно оба варианта тут: http://pastebin.com/scSwyuEq. Быстрая функция -- f, а медленная f1 (если захотите запустить медленную, то надо поменять имена.).

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Ну да сравнивать int'ы быстрее чем string'и, асимптотика та же, а константы другие.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Complexity doesn't matter too much when inputs are small, ex. insertion sort performs better than merge sort on small inputs, brute multiplication O(n^2) and FFT, and can become even worst, the constant factor can't be always ignored... it depends on processor architecture, caches... should not happen, but:
"In theory there is no difference between the theory and practice, in practice there is..."
→ Ответить