Упростить иногда пугающую концепцию

Всем привет. Это первая из серии статей, в которых я расскажу о концепциях информатики в упрощенных и понятных терминах. Исходя из моего личного опыта, несмотря на огромное количество ресурсов, новичку может быть сложно изучить новые концепции программирования. Это связано с тем, что многие источники часто объясняют их, используя излишне технический жаргон.

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

Давайте перейдем к нашей первой теме: нотации Big O.

Рассмотрим пример со мной: вы работаете волонтером на большой конференции и несете ответственность за то, чтобы дать каждому посетителю их именную бирку, когда они появятся. Вам дается стопка неупорядоченных визиток. Как вы будете выполнять эту задачу?

Первый и ужасно неэффективный способ выполнить эту задачу состоит в том, что для каждого человека, который появляется, вы просматриваете каждую карту в стопке, пока не найдете его визитку. Второй способ, возможно, тот, о котором вы только что подумали, - это разбить карточки на подгруппы на основе фамилий участников. Это может занять немного больше места на вашем столе, но тогда все, что вам понадобится, это фамилия участника, и вы сможете получить его карточку гораздо быстрее.

В этом примере вы можете увидеть, что существует множество различных способов решения проблемы. Мы учитываем две вещи: насколько быстро решение и сколько места занимает решение, чтобы определить, является ли оно «лучшим» вариантом. При измерении того, насколько что-то «быстро», мы можем буквально измерить точное количество секунд или минут, но это, возможно, не лучший способ. В первом решении, когда вы просматриваете каждую карту в стопке имен, чтобы найти имя, вам может повезти и вы найдете его немедленно, тогда как в других случаях вам может потребоваться время, чтобы просмотреть почти всю стопку, чтобы найти его. Поэтому измерение фактического времени для определения эффективности решения - не лучший вариант.

Вместо этого мы можем объяснить эффективность с помощью нотации Big O. Короче говоря, Big O отвечает на вопрос: как алгоритмическое решение работает с увеличением размера входных данных с точки зрения времени и пространства? В приведенном выше примере, что, если конференция теперь принимает дополнительно 1000 человек? Как ваше первое решение будет сравниваться со вторым? Подсказка: было бы еще хуже!

Ниже приведены некоторые распространенные случаи временной сложности и примеры из реальной жизни, которые помогут вам задуматься о них. В этих примерах n представляет размер ввода.

Примечание. В Интернете можно найти множество примеров анализа сложностей реального кода, поэтому я не буду их здесь рассматривать. Мой любимый урок - от Элвина из Coderbyte.

O (1) - Постоянная

  • Алгоритмическое решение занимает постоянное время, несмотря на размер входных данных.
  • Например, время, необходимое вам для уборки гостиной и подготовки к приему гостей, одинаково, независимо от того, сколько гостей вы ожидаете.

O (log n) - логарифмический

  • Время, необходимое для выполнения решения, описывается как логарифм размера ввода. Логарифм можно рассматривать как противоположность экспоненты: экспонента - это повторное умножение, а логарифм - это повторяющееся деление.
  • Например, вы ищете чье-то имя и номер в физической телефонной книге. Вам нужно разделить книгу пополам, посмотреть, находится ли имя человека в первой или второй половине, просмотреть эту половину и повторить. Каждый раз вы делитесь пополам, чтобы прийти к решению. Теперь, если телефонная книга станет немного толще (размер ввода увеличивается), не потребуется столько времени, чтобы найти имя и номер человека. Подумайте об этом в сравнении с решением, в котором вы буквально листаете страницу за страницей, чтобы найти информацию о человеке в книге. По мере увеличения объема книги вам потребуется гораздо больше, чтобы найти их. Это подводит нас к O (n).

O (n) - линейный

  • Время, необходимое для выполнения решения, увеличивается пропорционально размеру ввода. Если взять наш предыдущий пример, это будет подход «листать каждую страницу, пока не найдешь нужного человека».
  • Многие жизненные задачи выполняются с помощью среды выполнения Big O (n). Например, время, необходимое вам для складывания белья, зависит от размера вашей загрузки, а время, необходимое для того, чтобы вы дочитали книгу, зависит от того, сколько страниц в книге.

O (n²) - квадратичный

  • По мере увеличения размера ввода время, необходимое для выполнения алгоритма, увеличивается квадратично. Время - это квадрат размера ввода.
  • Например, предположим, что вы участвуете в надуманной группе отработки навыков собеседования с несколькими другими людьми. После того, как каждый человек по очереди попрактикуется в ответах на вопросы собеседования, все остальные в комнате по очереди высказывают свой отзыв. Общее время, необходимое для обратной связи, будет расти в геометрической прогрессии по мере того, как все больше людей присоединятся к группе подготовки к собеседованию, поскольку все должны идти, а все остальные должны давать отзывы после каждого хода.

Заключение

Надеюсь, эти примеры дали вам хорошее введение и лучший способ познакомиться с концепцией нотации Big O. Для дополнительных ресурсов, пожалуйста, проверьте: