Основы алгоритмов, часть 2: некоторые советы и рекомендации по вычислению временной сложности «большого нуля»…

Требования: базовые знания программирования на любом основном языке программирования (например, Python, Java, C++ и т. д.), основы математики (необязательно, но рекомендуется), знание асимптотических обозначений, используемых в информатике, таких как Ω-, O- и ϴ. -обозначения (в противном случае обратитесь к Части 1 для ознакомления)

Цель на сегодня

К концу статьи вы сможете рассчитать временную сложность алгоритмов, используя некоторые основные советы и рекомендации, обсуждаемые здесь.

Примечание. Мы предполагаем, что все циклы выполняются N раз или какое-то число, зависящее от N (например, N-1, N-2, N/2 и т. д.).

Один невложенный цикл:

Если наш алгоритм содержит один невложенный цикл, то T(N) = k * N, где k — некоторая константа (подумайте об этом как о времени, которое требуется вашему устройству для выполнения одной операции). Как мы уже обсуждали, по мере роста входного размера N такие константы, как k, становятся неактуальными, поскольку время вычислений описывается только входным размером N, а константы, такие как k, варьируются от устройства к устройству (или мы можем сказать, что время вычислений линейно чтобы ввести размер N). Итак, T(N) = O(N). Это означает, что сложность наихудшего случая линейно зависит от входного размера N.

Множественный невложенный цикл:

Если наш алгоритм содержит несколько невложенных циклов, то T(N) = c(kN), где c — количество циклов. С другой стороны, константы c и k становятся неактуальными по мере роста N. Итак, T(N) = O(N).

Вложенные циклы:

Если наш алгоритм содержит только один набор вложенных циклов, то T(N) = N^(k), где k — количество вложенных вместе циклов. В таком случае все время вычислений определяется каждым вложенным циклом, поскольку, поскольку количество итераций каждого цикла связано с N, все они вносят вклад во время вычислений. Следовательно, T(N) = O(N^(k))

Несколько вложенных циклов:

Предположим, у нас есть алгоритм, который выполняет определенную задачу, принимая на вход массив размера N. Затем мы можем создать функцию T(N), которая возвращает нам время, которое потребуется алгоритму для выполнения задачи над массивом размера N. Функция, скорее всего, будет полиномом вида:

T(N) = aN^(d) + bN^(d-1) +…+ cN, где a, b,…, c — константы.

Как мы обсуждали в предыдущей статье, по мере роста входного размера N сложность алгоритма в наихудшем случае (Big-O) определяется в основном членом с наивысшей степенью N. Следовательно, для любой функции T( N), будучи полиномом степени d. Сложность в худшем случае равна T(N) = O(N^(d)), где d — степень полиномиальной функции T(N).

Рекурсии:

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

Для рекурсий временная сложность Big-O определяется не только размером входных данных, но и тем, насколько сильно изменяется размер входных данных. По сути, нам нужно описать функцию T(N), которая сообщает нам, сколько раз функция будет рекурсивно вызывать сама себя до тех пор, пока не остановится для заданного входного размера N.

Например, возьмем функцию двоичного поиска.

BINARY_SEARCH(A, low, high, K):
  if low < high:
    mid = low+high / 2
    if A[mid] == K:
      return mid
    if A[mid] > K:
      return BINARY_SEARCH(A, low, mid, K)
    if A[mid] < K:
      return BINARY_SEARCH(A, mid, high, K)
  return -1

Здесь каждый раз, когда вызывается функция двоичного поиска, мы сжимаем диапазон входных данных вдвое. Диапазон варьируется от низкого к высокому, от низкого к высокому/2 или от высокого/2 к высокому. Функция T(N) будет примерно такой:

T(N) = {

-1, если низкий ≥ высокий

Mid, если A[mid] == K

T(N/2)

}

Отличный способ понять это — визуализировать это в виде дерева. После каждого вызова функции двоичного поиска размер входных данных уменьшается вдвое. Размер ввода будет продолжать делиться на 2 до тех пор, пока диапазон не станет 0, 1 или пока мы не найдем элемент.

Итак, если N кратно 2. Или N = 2^(i) для некоторого i, функция будет вызываться i раз. Следовательно, его временная сложность равна O(i). Используя логарифмы, мы можем сказать, что я = log2(N). Следовательно, T(N) = O(log2(N)).

ПРИМЕЧАНИЕ. Даже если N не кратно 2, мы все равно будем считать, что его временная сложность равна O(log2(N)), поскольку при этом добавляется только одно дополнительное вычисление, которое не имеет значения.

Вывод:

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