Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/3da/386/eed/3da386eed54c16ff73b647b383aea085.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/f54/446/a54/f54446a54f3d52d20e95ba5c5495644f.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/b91/1bc/ca9/b911bcca9ca9f9d8b0fa781a49118553.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/9a5/f72/788/9a5f72788d9e0e5ac0d0e585e3b3632f.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/373/6d4/4e7/3736d44e79e3bf542e2a847bbedcf86d.png)
Пусть дан граф с |V| вершинами и |E| ребрами, тогда
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/2da/7ae/feb/2da7aefeb058082fd3eaf1599f9500f8.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/fd0/c1c/9ed/fd0c1c9ed7d949c2cd258b45302016ca.png)
Короче говоря, если алгоритм имеет сложность __ тогда его эффективность __
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/17c/a73/d8d/17ca73d8dad367e1a60e3e20281e9d6d.png)
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/195/e1f/6a1/195e1f6a1379554ca9025338301a78ed.png)
![](https://habrastorage.org/getpro/habr/post_images/3da/386/eed/3da386eed54c16ff73b647b383aea085.png)
Поиск
![](https://habrastorage.org/getpro/habr/post_images/f54/446/a54/f54446a54f3d52d20e95ba5c5495644f.png)
Сортировка
![](https://habrastorage.org/getpro/habr/post_images/b91/1bc/ca9/b911bcca9ca9f9d8b0fa781a49118553.png)
Структуры данных
![](https://habrastorage.org/getpro/habr/post_images/9a5/f72/788/9a5f72788d9e0e5ac0d0e585e3b3632f.png)
Кучи
![](https://habrastorage.org/getpro/habr/post_images/373/6d4/4e7/3736d44e79e3bf542e2a847bbedcf86d.png)
Представление графов
Пусть дан граф с |V| вершинами и |E| ребрами, тогда
![](https://habrastorage.org/getpro/habr/post_images/2da/7ae/feb/2da7aefeb058082fd3eaf1599f9500f8.png)
Нотация асимптотического роста
![](https://habrastorage.org/getpro/habr/post_images/fd0/c1c/9ed/fd0c1c9ed7d949c2cd258b45302016ca.png)
- (О — большое) — верхняя граница, в то время как (Омега — большое) — нижняя граница. Тета требует как (О — большое), так и (Омега — большое), поэтому она является точной оценкой (она должна быть ограничена как сверху, так и снизу). К примеру, алгоритм требующий Ω (n logn) требует не менее n logn времени, но верхняя граница не известна. Алгоритм требующий Θ (n logn) предпочтительнее потому, что он требует не менее n logn (Ω (n logn)) и не более чем n logn (O(n logn)).
- f(x)=Θ(g(n)) означает, что f растет так же как и g когда n стремится к бесконечности. Другими словами, скорость роста f(x) асимптотически пропорциональна скорости роста g(n).
- f(x)=O(g(n)). Здесь темпы роста не быстрее, чем g (n). O большое является наиболее полезной, поскольку представляет наихудший случай.
Короче говоря, если алгоритм имеет сложность __ тогда его эффективность __
![](https://habrastorage.org/getpro/habr/post_images/17c/a73/d8d/17ca73d8dad367e1a60e3e20281e9d6d.png)
График роста O — большое
![](https://habrastorage.org/getpro/habr/post_images/195/e1f/6a1/195e1f6a1379554ca9025338301a78ed.png)