Невозможность выяснить эти жесткие примеры Big-O

Question

Я пытаюсь учиться на предстоящую викторину о нотации Big-O. У меня есть несколько примеров, но они дают мне неприятности. Они кажутся слишком продвинутыми для многих основных примеров, которые вы найдете в Интернете, чтобы помочь. Вот проблемы, на которые я застрял.

1.  `for (i = 1; i <= n/2; i = i * 2) { 
      sum = sum + product; 
      for (j= 1; j < i*i*i; j = j + 2) { 
       sum++; 
       product += sum; 
      } 
     }` 

Для этого одного, то i = i * 2 во внешнем контуре означает O (журнал (п)), и я не думаю, что состояние i <= n/2 меняет что-либо из-за того, как мы будем игнорировать константы. Таким образом, внешний цикл остается O (log (n)). Условие внутренней петли j < i*i*i меня смущает, потому что оно в терминах «i», а не «n». Будет ли Big-O этого внутреннего цикла быть O (i^3)? И, таким образом, Big-O для всей задачи be O ((i^3) * log (n))?

2.  `for (i = n; i >= 1; i = i /2) { 
      sum = sum + product 
      for (j = 1; j < i*i; j = j + 2) { 
       sum ++; 
        for (k = 1 ; k < i*i*j; k++) 
        product *= i * j; 
      } 
     }` 

Для этого один из самых внешних циклов подразумевает O (log (n)). Средний цикл подразумевает, опять же неуверенный, O (i^2)? И из самого внутреннего цикла следует O (i^2 * j)? Я никогда не видел таких примеров раньше, поэтому я почти догадываюсь об этом. Будет ли обозначение Big-O для этой проблемы O (i^4 * n * j)?

3.  `for (i = 1; i < n*n; i = i*2) { 
      for (j = 0; j < i*i; j++) { 
       sum ++; 
       for (k = i*j; k > 0; k = k - 2) 
        product *= i * j; 
      } 
     }` 

Наружный контур для этого есть^2 условие п, но и логарифмические приращения, так что я думаю, что уравновешивает быть только регулярным O (п). Средний цикл - O (i^2), а самый внутренний цикл - это просто O (n) и попытка обмануть вас. Итак, для этой задачи обозначение Big-O будет O (n^2 * i^2)?

4.  `int i = 1, j = 2; 
      while (i <= n) { 
       sum += 1; 
       i = i * j; 
       j = j * 2; 
     }` 

For this one I did a few iterations to better see what was happening: 
i = 1, j = 2 
i = 2, j = 4 
i = 8, j = 8 
i = 64, j = 16 
i = 1024, j = 32 

Так ясно, что «i» растет очень быстро, и, таким образом, условие выполняется очень быстро. Однако я не уверен, что это за формат Big-O.

Любые указатели, которые вы можете дать, очень ценятся, спасибо, ребята.

Answer 1

Вы не можете добавить i или j в O-нотацию, она должна быть преобразована в n.

Для первого:

Пусть к Log 2 я.

Затем внутренний цикл выполняется для каждого повторения внешней петли 2^(k * 3)/2 = 2^(3k-1) раз.

k переходит от 1 до log2n. Таким образом, общее число итераций составляет сумма 2^(3k-1) для k от 1 до log 2 n, которая равна 4/7 (n^3-1) согласно Wolfram Alpha, которая равна O (n^3) ,

Для последнего, я = j1 * j2 * j3 * ... Ю.К., и JM = 2^т

я = 2^1 * 2^2 * ... 2^к = 2^(1 + 2 + ... к)

Таким образом, 1 + 2 + 3 + ... + к = 2 н войти

(к + 1) к/2 = 2 н войти

Что такое O (sqrt (log n))

BTW, log n^2 не является n. Этот вопрос лучше задавать в информатике, чем здесь.