Вложенные циклы, сколько раз запускать и сложность

Question

У меня есть эти 2 кода, вопрос заключается в том, чтобы определить, сколько раз x = x + 1 будет запускаться каждый раз, поскольку T1 (n) обозначает код 1 и T2 (n) означает код 2. Затем я должен найти БОЛЬШОЙ O каждого из них, но я знаю, как это сделать, дело в том, что я застрял в поиске того, сколько раз (что касается n, конечно) будет x = x + 1 будет запустить.

КОД 1:

for(i= 1; i <= n; i++) 
    { 
    for(j = 1; j <= sqrt(i); j++) 
      { 
      for(k = 1; k <= n - j + 1; k++) 
       { 
       x = x + 1; 
       } 
      } 
    } 

КОД 2:

for(j = 1; j <= n; j++) 
    { 
    h = n; 
    while(h > 0) 
     { 
     for (i = 1; i <= sqrt(n); i++) 
      { 
      x = x+1; 
      } 
     h = h/2; 
     } 

    } 

Я действительно застрял, и прочитал уже много, так что я спросить, если кто-то может помочь мне, пожалуйста, объясните мне аналитически.

PS: Я думаю, что в коде 2 этот for (i = 1; i <= sqrt(n); i++) будет работать n * log (n) раз, правильно? И что?

Answer 1

Для code 1 у вас есть, что количество вызовов x=x+1 является:

Здесь мы ограничены 1+sqrt(2)+...+sqrt(n) с n sqrt(n) и использовали тот факт, что первый термин является ведущим термином.

Для code 2 расчеты проще:

Вторая петля на самом деле идет от h=n к 0 итерируя h = h/2 но вы можете видеть, что это то же самое, как происходит от 1 к log n. Мы использовали тот факт, что j, t, i взаимно независимы (аналогично тому, как мы можем записать, что сумма от 1 до n от f(n) составляет всего nf(n)).