Сравнение сложности времени - PullRequest
Новая
       9

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

0 голосов
/ 07 февраля 2019

Я получил эти два алгоритма с двумя циклами для каждого - первый алгоритм, по моему мнению, имеет квадратичное время работы.Второй алгоритм имеет то же время выполнения - O (n ^ 2)?

Алгоритм 1: 

for (int i = 1..n) { 
     for (int j = 1..n) {
          // sort m[i, j]
     } 
}

Алгоритм 2: 

for (int i = 1..n) { 
     for (int j = i..n) {
          // sort m[i, j]
     } 
}

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

Спасибо!

1 Ответ

0 голосов
/ 08 февраля 2019

Давайте проанализируем алгоритм 2, другой аналогичен.

Давайте сначала договоримся, что sort m[i, j] равно O((j-i)lg(j-i)). 

Alg 2  = O(sum_{i=1}^n sum_{j=i}^n (j-i)lg(j-i))
      <= O(sum_{i=1}^n sum_{j=i}^n (n-i)lg(n-i))
      <= O(sum_{i=1}^n (n-i)^2 lg(n-i))
       = O(sum_{i=1}^n i^2 lg(i))
      <= O(sum_{i=1}^n i^2 lg(n))
       = O(n^3 lg(n))

С другой стороны 

Alg 2  = O(sum_{i=1}^n sum_{j=i}^n (j-i)lg(j-i))                      ; take 1/2 of terms
      >= O(sum_{i=n/2}^n sum_{j=(i+n)/2}^n (j-i) lg(j-i))
      >= O(sum_{i=n/2}^n sum_{j=(i+n)/2}^n (n-i)/2 lg((n-i)/2)))      ; because j>=(i+n)/2
      >= O(sum_{i=n/2}^n ((n-i)/2)^2 lg((n-i)/2)))
      >= O(sum_{i=n/2}^{(n+n/2)/2} ((n-i)/2)^2 lg((n-i)/2)))          ; 1/2 of terms
      >= O(sum_{i=n/2}^{3n/4} (n/8)^2 lg(n/8))                        ; -i >= -3n/4
       = O(n^3 lg(n))
...