Лучше понять свои алгоритмы, чтобы вы могли их улучшить
Я очень взволнован этим постом, потому что он мой первый. После многих лет (и лет, и лет ...) откладывания я наконец начал это делать. Я надеюсь, вам понравится это чтение, но, более того, я надеюсь, что вы тоже кое-что узнаете.
Этот пост посвящен тому, сколько времени и пространства использует алгоритм. Хотя есть много математических выкладок, которые могут помочь нам вычислить эти вещи, мы сосредоточимся на интуитивном способе узнать эти измерения.
Я размещу ссылки в конце, если вы любите математику и хотите запачкать руки, но сначала давайте вспомним основы.
«Практически в каждом вычислении возможны различные схемы процессов. Важно выбрать такое расположение, которое минимизирует время, необходимое для расчета ». - Ада Лавлейс
Вернуться к основам
Что такое алгоритм?
Алгоритм (или метод) - это конечная последовательность инструкций, которая производит предсказуемый вывод из ввода. Это означает, что если последовательность инструкций не имеет определенного начала и конца, ее нельзя называть алгоритмом (цитируйте меня…).
Что такое c сложность?
Нет, я не спрашиваю, сложен ли ваш алгоритм для чтения, лол. Сложность - это мера времени или пространства алгоритма.
«Алгоритмы для компьютерных программ - это то же самое, что рецепты блюд. Различные рецепты могут помочь вам приготовить определенное блюдо, но они не всегда дают одинаковые результаты.
У них не всегда одни и те же шаги, ингредиенты и не всегда одинаковое количество времени. Некоторые рецепты быстрее и дают лучшие результаты, чем другие. - Сара Чима
Сложность времени
Сложность времени, представленная как T (n), - это количество времени, которое требуется для выполнения метода при размере ввода n.
Можем ли мы иметь разные значения для T (n) для алгоритма? Да, но как? Давайте посмотрим на простой пример.
Предположим, нам нужно отсортировать колоду карт.
У нас есть три возможных случая:
- В лучшем случае - для ввода требуется минимальное количество операций. Подумайте: колода уже отсортирована.
- Худший случай - для ввода требуется максимальное количество операций. Подумайте: колода полностью несортированная.
- Средний случай - для ввода требуется среднее количество операций. Подумайте: колода частично отсортирована.
Однако, если не указано иное, мы заботимся только о наихудшем случае для нашей временной сложности. Мы измеряем наихудший случай, используя нотацию big-O (big-oh).
Чтобы понять это на практике, давайте рассмотрим несколько примеров:
1. O (1) - Постоянное время
2. O (logn) - логарифмическое время.
3. O (n) - линейное время
4. O (nlogn) - линейное или логарифмическое время.
5. O (n²) - квадратичное время
6. O (2 ^ n) - экспоненциальное время
7. O (n!) - Факториальное время
Давайте попробуем несколько примеров
Какова временная сложность следующих алгоритмов? Вы согласны с моими ответами?
1. Обход многомерного массива
2. Метод Tomcat Embed Core getAllDeclaredMethods
Космическая сложность
Не так много (понятных) материалов о космической сложности; это намного менее популярно, но не менее важно.
Сложность пространства - это мера того, сколько памяти компьютера (ОЗУ) необходимо для выполнения алгоритма. Мы также можем выразить это с помощью большого О.
Давайте рассмотрим две реализации для возврата n-го числа Фибоначчи - рекурсивный (без мемоизации) и итеративный.
Надеюсь, вам понравилось, до скорой встречи!
Ресурсы и дополнительная информация
- Путь информатики: научитесь искусству решения вычислительных задач, Владстон Феррейра Филью
- Введение в нотацию большого О
- Почему метод сортировки массивов Java использует два разных алгоритма сортировки для сравнения?
- Квазилинейное время - Википедия
- YouTube видео (Немного математики для вас.)
Не стесняйтесь присылать мне дополнительные технические ссылки ниже, я добавлю их в сообщение!)
Особый привет: Владстон, ты долбаная легенда!