Решение T (n) временной сложности, содержащей «переменные» - PullRequest
Новая
       34

Решение T (n) временной сложности, содержащей «переменные»

0 голосов
/ 30 сентября 2018

Итак, мне нужно найти T (n) и затем Big-O (жесткая верхняя граница) для следующего фрагмента кода: 

int sum = 0;
for(int i = 1; i < n; i *= 2) {
    for(int j = n; j > 0; j /= 2) {
        for(int k = j; k < n; k += 2) {
            sum += i + j * k;
        }
    }
}

Теперь из того, что я вычислил для циклов, первый цикл запускается log (n) раз , второй цикл запускается (log (n) * log (n)) раз и третий цикл вызывает путаницу, потому что я считаю, работает для (n - j) / 2 раза .Мой вопрос: могу ли я предположить, что это будет n / 2 раза , потому что я думаю, что это не будет жесткой верхней границей, если я это сделаю.Или есть другой подход, который мне не хватает?

Ответы [ 2 ]

0 голосов
/ 30 сентября 2018 
for(int i = 1; i < n; i *= 2) // (1)
    for(int j = n; j > 0; j /= 2) // (2)
        for(int k = j; k < n; k += 2) // (3)

Для первой итерации (3) (где k = j = n) итерации не будет.После деления j на 2 третий цикл будет выполняться (n / 2) / 2 или n / 4 раза.После третьей итерации (2), (3) будет выполняться n / 4/2 или n / 8 раз.Мы можем суммировать время выполнения следующим образом: 

n/4 + n/8 + n/16 + ... + n/2^k

Это также можно записать в виде: 

n * (1/4 + 1/8 + 1/16 + ... + 1/2^k)

Асимптотически в O(n).

0 голосов
/ 30 сентября 2018

Это очень интересный вопрос.Давайте дадим n реальное число и посмотрим, как оно происходит.Скажи, n=100.Если мы посмотрим только на два внутренних цикла 

j        k
100      None
50       50, 52, ..., 98
25       25, 27, ..., 99
12       12, 14, ..., 98
6        6, 8, ..., 98
3        3, 5, ..., 99
1        1, 3, ..., 99

Как вы можете видеть, сложность третьего цикла фактически равна O(n).Особенно, когда n очень большое число, оно будет близко к Θ(n)

...