Как найти временную сложность (Big O) этого блока кода?

Question

Я пытаюсь понять, как работает эта нотация O, и здесь у меня есть блок кода, а рядом с каждой LINE у меня будет комментарий с временной сложностью, на которую я полагаю. Если я ошибаюсь, исправьте меня и объясните, почему моя логика неправильна.

код # 1

for (int i = 0; i < n; i++) <<<<<<<<<<<<<<<<<<< O(1)*O(N) 
{ 
    for (int j = 0; j < 3; j++) <<<<<<<<<<<<<<< O(1)*O(1) 
     { 
     for (int k = 0; k < 3; k++) <<<<<<<<<<<<<<O(1)*O(1) 
      { 
      printf("%d", arr[i]); <<<<<<<<<<<<<<O(1) 
      } 
     printf("\n"); <<<<<<<<<<<<<<<<<<O(1) 
    } 

} 

Хронометраж = O (N), после добавления все.

код # 2

for (int i = 2; i <= n; i++) <<<<<<<<<<<<O(1)*O(N) 
{ 
     int j;<<<<<<<<<<<<<<<<<<<<<<<O(1) 
     printf("\n%d:", i);<<<<<<<<<<<<<<O(1) 
     for(j = 2; j <= i; j = j * 2) <<<<<<<<<<<O(n-2)?????????? 
     { 
      printf("%d ", j);<<<<<<<<<<<<<<O(1) 
     } 
     printf("\n%d:", i);<<<<<<<<<<<<<<<<<<<<O(1) 
     for(int k = j/2; k >= 2; k = k/2)<<<<<<<<<<<<<I am not sure of this one 
     { 
      printf("%d ", k); 
     } 
    } 

Продолжительность: Неуверенный ..

В целом, я Любопытный получить представление о нем, но еще не до конца уверен в том, как использовать его в некоторых ситуациях. У кого-нибудь еще есть руководство или какой-то вид, который дает примеры и объяснения временной сложности для циклов и циклов?

Answer 1

блок k равен O(lg j), где j равно O(n), поэтому k равно O(lg n). но если вы рассматриваете всю программу, это O(n lg n).

Answer 2

Вот правила:

• Loop является число итераций раз сложности тела
• Последовательные блоки являются суммой сложностей
  • Но в O() только асимптотически наибольший член имеет значение, поэтому вы можете сразу упростить до более сложной сложности
• Мультипликативные константы неактуальны
• Геометрическая прогрессия (j петля с j = j * 2 и k петля с k = k/2) имеет сложность O(log n)