Какая будет временная сложность этого алгоритма

Question

Я новичок в соревновательном программировании и нотации Big O.

public void function(int n){
   for(int i = n; i > 0; i/=3){
       for(int j = 0; j < i; j++){
           System.out.println("Hello");
       }
   }
}

Это алгоритм. Насколько я знаю о временной сложности. Она определяет, как время выполнения зависит от количества входов.

Итак, если мы возьмем пример, если 'n' равно 10. Внешний l oop запускает log n раз, а внутренний l oop выполняется i раз.

внутренний l oop выполняется относительно i, а не n. Поэтому я немного запутался в том, как рассчитывается временная сложность. Я думаю, что это O (log n). Пожалуйста, поправьте меня, если я ошибаюсь.

Будет ли это O (log n), O (n log n) или (n ^ 2). Пожалуйста, помогите мне с этим. Спасибо.

Answer 1

Я попытаюсь объяснить это самым простым языком

Внешний l oop просто запустит log (n) с базой 3 раза.

Поскольку, i уменьшается на фактор 3 каждый раз. Общая проделанная работа равна:

n + n / 3 + n / 9 + n / 27 + .... n / (3 ^ log (n))

, поскольку, n / 3 + ... + n / (3 ^ log (n)) всегда будет меньше n

, например, пусть n = 100, тогда 100 + 100/3 + 100/9 + 100 / 27 + ... = 100 + (33,3 + 11,11 + 3,7 + ...)

ясно видно, что члены в скобках всегда будут меньше 100

Общая временная сложность общего решения будет O (n).

Answer 2

Так что это отличный вопрос! Это сложный вопрос, который требует немного больше размышлений для анализа.

Как правильно указано в некоторых других ответах, внешний l oop:

for(int i = n; i > 0; i/=3)

будет запускать log (n ) раз. В частности, log_3 (n) раз, но в большой нотации O мы не часто беспокоимся о базе, поэтому log (n) подойдет.

Теперь вложенный l oop немного сложнее:

for(int j = 0; j < i; j++){

На первый взгляд вы можете подумать, что это простой журнал (n) l oop, но давайте посмотрим немного дальше. Таким образом, на первой итерации это будет выполнено N раз, так как значение i будет n. На следующей итерации он будет запущен n / 3 раз. Тогда n / 9, n / 27, n / 81 и т. Д. c ....

Если мы просуммируем этот ряд, ясно, что он составит меньше 2n. Следовательно, мы можем заключить, что этот алгоритм имеет сложность O (n).

Answer 3

для вашего кода:

for(int i = n; i > 0; i/=3){
   for(int j = 0; j < i; j++){
       System.out.println("Hello");
   }

}

Внутренний l oop переменная j зависит от внешней l oop переменной i, поэтому ваш внутренний l oop будет тот, который определит сложность вашего алгоритма. так как j будет выполняться n раз в первом прогоне, n / 3 раз во втором прогоне и так далее ... поэтому ваша общая сложность может быть рассчитана как

n + n / 3 + n / 9 + n / 27 + .......

, что дает O (n)

Answer 4

На самом деле он никогда не прекратится, причина i=0, а обновление - i *= 3, поэтому i останется 0, поэтому мы можем сказать O(+oo)

, если вы имели в виду for(int i =1..., тогда его O(n):

• Внешний l oop явно O(log_3 n) потому что мы продолжаем умножать на 3
• Внутренний l oop будет выполнено O(log_3 n) раз с количеством итераций из (1 + 3 + 9 + 27 + ... + 3^log_3(n)), что явно представляет собой геометрическую c прогрессию, решение которой дает нам приблизительно 3^log_3(n)), что в соответствии с правилами журнала дает n, поэтому этот l oop занимает O(n) для всех итераций, поэтому общая сложность составляет O(n)

Answer 5

В фрагменте кода:

for (int i=0; i < n; i*=3) { 
    for (int j=0; j < i; j++) {
        System.out.println("Hello");
    }
}

Внешний l oop в i равен O(log_3(n)), потому что каждое приращение l oop уменьшает количество земли, необходимое для i для достижения n с коэффициентом 3. Это логарифмическое поведение c (log_3 в данном случае). Внутренний l oop в j просто повторяется столько же раз, сколько и внешнее значение i, поэтому мы можем просто возвести в квадрат внешнюю сложность, чтобы получить:

O(log_3(n)^2)