Кратко говоря, теория сложности — это наука о том, насколько сложны алгоритмы. Чтобы быть полезным, у любого алгоритма должно быть 3 ключевых свойства:
- Он должен быть корректен. Какой от него толк, если он не дает правильные ответы.
- Хороший алгоритм должен быть понятен. Даже самый лучший алгоритм не даст пользы, если его слишком сложно реализовать на компьютере.
- Хороший алгоритм должен быть эффективным. Даже если алгоритм дает корректный результат, он не сильно поможет, если для этого потребуется тысячи лет или миллиард терабайтов памяти.
Теория сложности изучает последнее свойство алгоритмов (Хороший алгоритм должен быть эффективным).
Есть несколько типов сложности, первый и самый очевидный тип — это временная сложность. Многие алгоритмы ограничены своей скоростью, поэтому важно знать, сколько времени требуется алгоритму, чтобы решить задачу.
Второй тип — это пространственное сложность. Некоторые алгоритмы использует много памяти или дисковое пространство. Например, хеш таблицы используют больше пространство чем другие структуры данных и это позволяет им находит элементы очень быстро. Другие алгоритмы могут использовать и другие ресурсы, например, алгоритму может требоваться сетевое взаимодействие, в этом случае программа может быть ограничена ширеной канала. Еще алгоритмы могут полагаться на графические ресурсы и также на другие типы оборудование, например, принтеры, 3D принтеры, CPU, сенсоры и другие.
Нужно понимать условия работы алгоритма. Самая простая ситуация — это когда алгоритм дает одинаковую производительность в каждом случае, не важно какие входные данные, производительность не меняется. Но тем не менее производительность некоторых алгоритмов зависит от входных данных. Некоторые алгоритмы хорошо справляются с одним набором данных, но ужасно с другим. Например, такое поведение есть у алгоритма быстрой сортировки. Это очень быстрый алгоритм для сортировки рандомных / случайных чисел, но если числа уже отсортированы, то он становится ужасно медленным.
Для таких алгоритмов, как быстрая сортировка, нужно учитывать поведение в лучшем случае, среднем и худшем случае. Чтобы быть в безопасности, люди часто концентрируются на наихудшем случае. Для многих алгоритмов также полезно рассмотреть ожидаемое случае. В случаи с быстрой сортировкой большинство приложение сортируют более или менее рандомные данные, в этом ожидаемом случае быстрая сортировка работает хорошо.
Теперь вы знаете о типах сложности и условиях, которые могут дать разное поведение. Возможно, вы задались вопросом — Зачем об этом беспокоиться? действительно ли нужно анализировать алгоритм, чтобы доказать его поведение? Нельзя ли просто выполнить его и посмотреть, подходит или нет? Ответ — конечно можно! Попробуйте алгоритм и посмотрите, что произойдет. Но если алгоритм недостаточно быстро работает или у вас недостаточно памяти, то вы потратите много времени. А можно было сразу предсказать, что алгоритм работать не будет. Это одна из причин изучать сложность алгоритмов, уметь предсказывать их поведение. Другая причина — это сравнение производительности с другими алгоритмами. Если вы знаете, что вы будете сортировать уже по большей части отсортированные данные, то используйте сортировку пузырьком, она плоха для рандомных данных, но быстро работает, если данные в основном сортированы.
Если вы понимаете разницу между быстрой сортировкой и сортировкой пузырьком, то сможете выбрать правильную для свои задачи. И конце концов, изучение сложности поможет вам доказывать характеристики алгоритма. Например, криптографические алгоритмы делают очень сложную расшифровку сообщение, если вы не знаете ключ, с которым оно было зашифровано. Это один из тех случаев, когда нужно чтобы алгоритм было медленным. Атакующий может взломать код и увидеть сообщение, но это не важно, если для расшифровки сообщений может потребоваться много лет.
Комментарии