Лучше понять свои алгоритмы, чтобы вы могли их улучшить

Я очень взволнован этим постом, потому что он мой первый. После многих лет (и лет, и лет ...) откладывания я наконец начал это делать. Я надеюсь, вам понравится это чтение, но, более того, я надеюсь, что вы тоже кое-что узнаете.

Этот пост посвящен тому, сколько времени и пространства использует алгоритм. Хотя есть много математических выкладок, которые могут помочь нам вычислить эти вещи, мы сосредоточимся на интуитивном способе узнать эти измерения.

Я размещу ссылки в конце, если вы любите математику и хотите запачкать руки, но сначала давайте вспомним основы.

«Практически в каждом вычислении возможны различные схемы процессов. Важно выбрать такое расположение, которое минимизирует время, необходимое для расчета ». - Ада Лавлейс

Вернуться к основам

Что такое алгоритм?

Алгоритм (или метод) - это конечная последовательность инструкций, которая производит предсказуемый вывод из ввода. Это означает, что если последовательность инструкций не имеет определенного начала и конца, ее нельзя называть алгоритмом (цитируйте меня…).

Что такое c сложность?

Нет, я не спрашиваю, сложен ли ваш алгоритм для чтения, лол. Сложность - это мера времени или пространства алгоритма.

«Алгоритмы для компьютерных программ - это то же самое, что рецепты блюд. Различные рецепты могут помочь вам приготовить определенное блюдо, но они не всегда дают одинаковые результаты.

У них не всегда одни и те же шаги, ингредиенты и не всегда одинаковое количество времени. Некоторые рецепты быстрее и дают лучшие результаты, чем другие. - Сара Чима

Сложность времени

Сложность времени, представленная как T (n), - это количество времени, которое требуется для выполнения метода при размере ввода n.

Можем ли мы иметь разные значения для T (n) для алгоритма? Да, но как? Давайте посмотрим на простой пример.

Предположим, нам нужно отсортировать колоду карт.

У нас есть три возможных случая:

  1. В лучшем случае - для ввода требуется минимальное количество операций. Подумайте: колода уже отсортирована.
  2. Худший случай - для ввода требуется максимальное количество операций. Подумайте: колода полностью несортированная.
  3. Средний случай - для ввода требуется среднее количество операций. Подумайте: колода частично отсортирована.

Однако, если не указано иное, мы заботимся только о наихудшем случае для нашей временной сложности. Мы измеряем наихудший случай, используя нотацию 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-го числа Фибоначчи - рекурсивный (без мемоизации) и итеративный.

Надеюсь, вам понравилось, до скорой встречи!

Ресурсы и дополнительная информация

Не стесняйтесь присылать мне дополнительные технические ссылки ниже, я добавлю их в сообщение!)

Особый привет: Владстон, ты долбаная легенда!