Рубрики

Анализ алгоритмов | Набор 4 (анализ циклов)

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

1) O (1): временная сложность функции (или набора операторов) рассматривается как O (1), если она не содержит цикл, рекурсию и вызов любой другой непостоянной временной функции.

   // set of non-recursive and non-loop statements

Например, функция swap () имеет временную сложность O (1).
Цикл или рекурсия, которая выполняется постоянное число раз, также рассматривается как O (1). Например, следующий цикл — это O (1).

   // Here c is a constant   
   for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

2) O (n): временная сложность цикла рассматривается как O (n), если переменные цикла увеличиваются / уменьшаются на постоянную величину. Например, следующие функции имеют O (n) временную сложность.

   // Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

3) O (n c ) : временная сложность вложенных циклов равна числу выполнений самого внутреннего оператора. Например, следующие примеры циклов имеют O (n 2 ) временную сложность

  
   for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i -= c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

Например, сортировка выбора и сортировка вставкой имеют O (n 2 ) временную сложность.
4) Время O (Logn) Сложность цикла рассматривается как O (Logn), если переменные цикла делятся / умножаются на постоянную величину.

   for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

Например, бинарный поиск (см. Итеративную реализацию) имеет временную сложность O (Logn). Давайте посмотрим математически, как это O (Log n). Ряд, который мы получаем в первом цикле: 1, c, c 2 , c 3 ,… c k . Если мы положим k равным Log c n, мы получим c Log c n, который равен n.
5) Время O (LogLogn) Сложность цикла рассматривается как O (LogLogn), если переменные цикла уменьшаются / увеличиваются экспоненциально на постоянную величину.

   // Here c is a constant greater than 1   
   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }
   //Here fun is sqrt or cuberoot or any other constant root
   for (int i = n; i > 1; i = fun(i)) { 
       // some O(1) expressions
   }

Смотрите это для математических деталей.
Как совместить временные сложности последовательных циклов?
При наличии последовательных циклов мы вычисляем сложность времени как сумму временных сложностей отдельных циклов.

   for (int i = 1; i <=m; i += c) {  
        // some O(1) expressions
   }
   for (int i = 1; i <=n; i += c) {
        // some O(1) expressions
   }
   Time complexity of above code is O(m) + O(n) which is O(m+n)
   If m == n, the time complexity becomes O(2n) which is O(n).   

Как рассчитать сложность времени, когда внутри циклов много операторов if, else?
Как обсуждалось здесь , сложность времени в наихудшем случае является наиболее полезной среди лучших, средних и худших. Поэтому нам нужно рассмотреть наихудший случай. Мы оцениваем ситуацию, когда значения в условиях if-else приводят к выполнению максимального количества операторов.
Например, рассмотрим функцию линейного поиска, где мы рассматриваем случай, когда элемент присутствует в конце или не присутствует вообще.
Когда код слишком сложен, чтобы рассматривать все случаи if-else, мы можем получить верхнюю границу, игнорируя if else и другие сложные операторы управления.
Как рассчитать временную сложность рекурсивных функций?
Временная сложность рекурсивной функции может быть записана как математическое рекуррентное отношение. Чтобы вычислить сложность времени, мы должны знать, как решать повторения. Вскоре мы будем обсуждать методы решения рецидивов отдельным постом.

Викторина по анализу алгоритмов

Далее — Анализ алгоритма | Набор 4 (решение повторений)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Анализ алгоритмов | Набор 4 (анализ циклов)

0.00 (0%) 0 votes