Big O
Как се мисли за сложността на алгоритъм. Big O, чести капани и какво всъщност търсят интервюиращите.
Какво значи "оптимизирам"
Оптимизация = правиш нещо по-добро по даден критерий. Но винаги има цена. По-бързо често значи "ползва повече памет". По-малко памет често значи "повече смятане". Първият въпрос не е "как", а "по кое и срещу какво".
1) Какво искам да подобря (време, памет, заявки)? 2) Защо точно това (има ли реален проблем)? 3) Какви са ограниченията (deadline, hardware, бюджет)? Без отговор и на трите, "оптимизирам" е празна дума.
Big O гледа какво става при големи входни данни
При малки входове съвременният компютър е достатъчно бърз - почти всеки алгоритъм работи мигновено. Истинската разлика се вижда при голямо N: милион, милиард записи. Там константите изчезват и формата на функцията започва да определя дали скриптът ще приключи за секунди или за дни.
„Big O measures algorithm performance with input going to infinity.“
Кошница с яйца и тиган: три различни алгоритъма
Имаш N яйца в кошница и един тиган. Разстоянието от кошницата до тигана е C стъпки. Целта е всички яйца да попаднат в тигана. Има различни начини да го направиш - и всеки начин има различна сложност.
O(1) - константа
Един курс, готово
Прегръщаш цялата кошница, занасяш я наведнъж до тигана. Дали са 3 или 3 милиона яйца, броят стъпки е един и същ. Не зависи от N.
O(n) - линейно
По едно яйце на курс
Носиш едно яйце, връщаш се за следващото. За N яйца правиш N курса напред и назад. Общо движение: 2*N*C. Расте линейно с N.
O(n²) - квадратично
Допълнителни курсове на ход
Носиш k-тото яйце, но преди да продължиш правиш още k пъти отиване-връщане. Сумата 1+2+...+N = N*(N+1)/2 курса. Расте с N на квадрат.
Сложностите от най-добра към най-лоша
Ето как се държат най-често срещаните сложности при растящ вход. Зелено = бързо. Жълто = започва да дърпа. Тъмно = практически невъзможно за реални данни.
| Сложност | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | 3 | 10 | 20 |
| O(n) | 10 | 1K | 1M |
| O(n log n) | 33 | 10K | 20M |
| O(n²) | 100 | 1M | 10¹² |
| O(n³) | 1K | 10⁹ | 10¹⁸ |
| O(2ⁿ) | 1K | 10³⁰¹ | няма |
| O(n!) | 3.6M | няма | няма |
Технически съществуват, но в реални алгоритми се срещат изключително рядко. Когато ти излезе нещо като O(n⁶), почти винаги има по-добро решение, което някой вече е намерил. В практиката си говорим основно за O(n²) и O(n³) - те покриват 99% от случаите.
Буквата "n" в Big O не е името на твоя параметър
Това е грешката, която много хора правят на whiteboard интервюта. "Iterate-вам матрица M x N, значи сложността е O(N)" - НЕ. "n" в Big O е общият размер на входа, не променливата, която кодът ти е кръстил "n".
Big O винаги се изразява спрямо общия размер на входа. Ако имаш 4 параметъра a, b, c, d, сложността пак се пресмята спрямо тяхното произведение или сума, не спрямо буквичките в подписа.
5 стъпки за оптимизация на алгоритъм
- 1Намери работещо решение. Каквото и да е, само да решава задачата.
- 2Анализирай time и space complexity на това, което имаш.
- 3Подобри: (a) намали time без да влошиш space; (b) намали space без да влошиш time; (c) ако може, и двете.
- 4Имплементирай оптималния вариант.
- 5(Бонус) Докажи, че няма по-добро решение от това.
Помисли: ако носиш по 1 яйце и за всяко доставено правиш k допълнителни курса (1 за първото, 2 за второто, ...), общият брой курсове е 1+2+...+N. Каква сложност излиза? И как би изглеждал алгоритъм, който наистина е O(2ⁿ)? Пиши отговора в коментарите под видеото.
Кратко 4-минутно обяснение за бърз reset на основните понятия. Добро допълнение преди интервю.
Визуално обяснение с диаграми за това как се движат различните сложности при растящ вход. Полезно ако "виждаш" по-добре, отколкото четеш.
Лекция 2: Комбинаторика
Пермутации, вариации, комбинации, биномни коефициенти. Защо точно тези понятия се появяват навсякъде в анализа на сложност и в data-heavy задачи. Следва всеки втори вторник нова лекция.
Към следващата лекция