Это первая статья из серии статей, в которых я буду освещать важные аспекты структур данных и алгоритмов. В этой статье мы поговорим о временной сложности. Условие: вложенные циклы, операторы if-else.

Основная терминология:

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

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

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

Почему и где временная сложность:

В общих случаях построение алгоритма связано с двумя основными случаями:

  1. Вам дали задачу в конкурентной среде для решения.Конкурентная среда может относиться к соревнованию по программированию, в котором вы участвуете, или к решению задачи на одном из онлайн-судей. Если проблема публикуется на сайте, то гарантируется, что по крайней мере один человек уже решал эту задачу (автор). Он ожидает, что мы найдем решение его проблемы. Для решения задачи разрабатываем ряд задач или алгоритм.
  2. Нас просят разработать алгоритм для совершенно новой задачи (той, которая не была решена раньше):Здесь мы пытаемся быть автором. Это непростая работа, потому что нам нужно начинать с нуля и реконструировать наш путь через проблему, чтобы найти решение (которое еще никто не нашел).

В обоих этих случаях давайте предположим, что мы придумали несколько правильных алгоритмов для решения проблемы. Этим алгоритмам потребуется определенное время для запуска и получения результата, потому что ПК может выполнять только заданное количество операций за период времени. .(Число операций здесь является верхней границей). Существует определенный временной лимит, в который должен вписаться наш алгоритм. Этот срок варьируется для разных задач. Алгоритм, который требует минут или часов для решения проблемы, которую можно решить за секунды, бесполезен для нас. Теперь мы не можем написать наш код, запустить, а затем проверить, укладывается ли наш алгоритм в требуемый лимит времени, потому что это слишком громоздкая задача. Если бы мы каким-то образом смогли вычислить (даже до написания всего кода) время, затрачиваемое этими алгоритмами на решение, это творило бы чудеса. Именно здесь вступает в игру временная сложность с использованием асимптотической записи. Временная сложность помогает нам использовать функцию (которая зависит от размера входных данных) для количественной оценки количества операций, выполняемых в алгоритме. Вы, должно быть, уже поняли, что операции в алгоритме зависят от размера входных данных. Единственным исключением из этого правила является случай, когда алгоритм работает за постоянное время.

Асимптотическая запись

Время, необходимое алгоритму для завершения, подпадает под 3 категории:

  1. Оптимальный вариант: минимальное время, необходимое для выполнения программы.
  2. Средний случай : среднее время, необходимое для выполнения программы.
  3. Худший случай: максимальное время, необходимое для выполнения программы.

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

Для изображения временной сложности используются три асимптотических обозначения:

  1. нотация омега (Ω) : представляет наилучшую сложность случая или наилучшее время, которое может потребоваться для завершения алгоритма. Более формально он представляет собой нижнюю границу времени работы алгоритма.
  2. тета-нотация (Θ) : представляет среднюю сложность случая или среднее время, которое может потребоваться для завершения алгоритма. Более формально он представляет как верхнюю, так и нижнюю границу времени выполнения алгоритма.
  3. нотация big-O (O) : представляет наихудшую сложность или наихудшее время, которое может потребоваться для завершения алгоритма. Более формально он представляет собой верхнюю границу времени работы алгоритма.

Пусть размер входных данных для нашей задачи равен «n». Тогда, если бы алгоритм линейно зависел от размера входных данных, мы могли бы записать временные сложности как Ω(n), Θ(n) или O(n), в зависимости от нашего алгоритма.

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

Обратите внимание, чтомы никогда не говорим о фактическом времени выполнения алгоритма, поскольку оно нам не нужно. Одни машины быстрые, другие медленные. Нет смысла знать или вычислять время выполнения всех алгоритмов на разных машинах. Вот почему мы формулируем анализ с точки зрения «количества операций», а не «времени выполнения». С этой идеей исчезает представление о быстрой или медленной машине.

Время Сложность некоторых простых операций

  1. Математические операции . Предполагается, что они занимают время O(1), т. е. постоянное время, независимо от размера обрабатываемых чисел.
  2. Инструкции if-else: они также занимают время O(1).
  3. Циклы: они занимают время O(n), если цикл выполняется от 0 до n, потому что мы будем повторять каждое из чисел от 0 до n.
  4. Странные и не очень странные комбинации вышеперечисленного :
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        Some Operation;
    }
}

«Некоторая операция» будет выполняться n*m раз из-за вложенных циклов for. Это займет порядка O (n * m) времени.

int t = p;
while(p--){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            Some Operation;
        }
    }
}

Здесь «Некоторая операция» будет выполняться p*n*m раз из-за вложенных циклов for и while. Это заняло бы время O(p*n*m).

int p = a;
if(p == 6){
   for(int i = 0; i < n; i++){
       Some Operation;
   }
}
else{
    Same Operation as above;
}

Здесь «Некоторая операция» будет выполняться только в том случае, если a == 6. Но, поскольку мы говорим о наихудшей сложности, мы должны это учитывать. Следовательно, это займет время O (n). (Помните, что if-else занимает время O(1)).

for(int i = 0; i < n; i++){
    Some Operation;
}
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        Some Operation;
    }
}

Здесь временная сложность будет порядка O(n + n²). Когда n очень велико, n² намного больше, чем n, и становится доминирующим фактором для функции.В подобных ситуациях мы учитываем только члены высшего порядка! Таким образом, сложность будет порядка O(n²). Кроме того, константы не имеют значения при рассмотрении временной сложности. Таким образом, O(3n² + 5n) эквивалентно O(n²). Это связано с тем, что и 3n², и 6n² (просто пример) изменяются с одинаковой скоростью, т.е. если вы удваиваете ввод, время увеличивается в четыре раза. Так что на самом деле не имеет значения, какую константу мы выберем.

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

Примечательно, что разные источники сообщают разные цифры общего количества операций, которые могут быть выполнены за секунду на машине. Число колеблется от 10⁶ до 10⁹. Мы постараемся удержать количество операций в наших алгоритмах в пределах этого диапазона.

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

Удачного кодирования :)