http://bigocheatsheet.com/

Отличная шпаргалка. Сесть и помедитировать. Еще раз уложить в голове эти вещи. Если у кого-то есть любые вопросы – спрашивайте.

Я сделал всего ДВА скриншота. По ссылке информации много больше.

Что эти все O(n*log(n)) означают на практике:

Характеристики структур данных:

Задачки на осознание

1) В каких ситуациях QuickSort (“Best ever”, фактически стандарт сейчас) может дать “плохой” результат, хуже любого другого алгоритма (дает (O(n^2)).

2) В каких случаях Insert Sort (или BubbleSort) рвет все другие алгоритмы сортировки (выдают O(n))? // hint: частично отсортированные данные

3) В каких случаях HashTable превращается в LinkedList (со всеми вытекающими) и что с этим делать? // hint: алгоритм хэширования

4) Ваш алгоритм на HashTable стал потреблять слишком много памяти, что можно сделать? // hint: найти другую структуру данных, можно по шпаргалке выше.

5) ….

… … …

Практика. Какая разница между O(n^2) и O(n log(n))?

Пару лет назад я спасал Эндо (так и не спас, by the way). Так вот, O(n^2) давало 2.7 mil ops/day, а O(n log(n)) дало те же 2250 ops/мин Это чтобы оценить порядки. Хотя стоит сказать, что задача была совсем не типична для нашей работы.

Ну и чтобы не быть совсем голословным про O(n) и O(log(n)).

До оптимизации:

я до сих пор не видел картинки грустного Эндо. Нужно ускорять алгоритм трансформации. Скорость, почему-то, упала в 3 раза. Теперь одна иерация занимает ~90ms. Вчера меня хватило только на 15 минут: 10 000 итераций, 5000 РНК команд. Так как в результате я увидел только кусок неба, итераций должно быть не в пример больше.

После оптимизации (Одну из n превратил в log(n)):

Ускорил трансформацию. 1 891 886 итераций за 13 минут = 2250 оп/мин

Оказалось, что самое сложное это не запрограммировать структуру данных, хранящую кусочки строки, а реализовать строковые функции для кусочков. Например поиск подстроки в строке я реализовал только с помощью тестов. Тупо напсал тест, который проверяет функцию на рандомных данных и разбирался что я не так сделал. Тот еще челенж был. Еще, впервые в жизни осознал, что logN шопипец как круче чем N (ускорение программы на несколько порядков).

Но, с другой стороны, использование нужного алгоритма или структуры данных может превратить десятки минут или часов в минуты и даже секунды. Каждый раз когда делаете долгие вычисления думайте об этом.

P.S. Если кто-то хочет спасти Эндо (я не спас, но хоть нашел)

Для затравки мое описание задачи, более интересно и даже захватывающе от Адепта.

1) Если кто хочет попробовать алгоритмы и оптимизации на интересной задачке, то вам кроме задания ничего не нужно http://save-endo.cs.uu.nl/

2) Если вам интереснее порешать IT головоломки, то можно взять мою реализацию (делает картинку за 1,5 минуты, есть даже визуализатор) и вперед (ссылка на битбакет)

1) я сделал, 2) уже нет. Получил много фана. Особенность этой задачки в том, что ее можно решать оффлайн – сервер организаторов не нужен. На одном из собеседований, где просили пример кода, этот репозиторий меня неплохо выручил. Код действительно не стыдно показывать.