Сколько раз выполняется этот двойной цикл?

Question

void runner(int n, int a, int b){ 
    for(int i = 1; i <= n; i *= a) 
     for(int j = 1; j <= i*b; j++) 
      //run something here 
} 

Есть ли простой способ определить, сколько раз «запускать что-то здесь» будет выполнено?

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

Answer 1

void runner(int n, int a, int b){ 
    int counter=0; 
    for(int i = 1; i <= n; i *= a) 
     for(int j = 1; j <= i*b; j++) 
      counter++; 

    PRINT COUNTER'S VALUE 
} 

Используйте отладчик, чтобы узнать, как именно счетчик увеличивается.

Answer 2

1. Объявляет новый ИНТ и придать ему значение «0»
2. Сделать внутреннее приращение цикла, что новый Int (где ваш комментарий)
3. Сделать это распечатать Int в конце или внутри цикла
4. Посмотрите на результат

Java Пример:

void runner(int n, int a, int b){ 
    int x = 0; 
    for(int i = 1; i <= n; i *= a) 
     for(int j = 1; j <= i*b; j++) 
      x++; 
      System.out.println(x); 
} 

Answer 3

Общий рецепт: написать точную формулу и посмотреть, как вы можете ее упростить.

В наружном контуре, то i переменная изменяется как 1, затем a, затем a*a и так далее. Для каждого значения i внутренний цикл работает b*i раз. Таким образом, у нас есть исполняющая среда

b + b*a + b*a*a + ... + b*a^k 

где ^ означает силу и k=floor(log_a(n)) (base- a логарифм здесь).

Это подводит к

b*(1 + a*a + ... + a^k) = b*(a^(k+1)-1)/(a-1) 

Это точный ответ. Для O -notation или для приближенных значений, можно предположить, что a^(k+1) приблизительно n (хотя примечание ниже), поэтому время автономной работы

b*(n-1)/(a-1) 

Для больших n и a мы имеем

b*n/a 

Примечание: фактически для больших a допущение, что a^(k+1) is n может быть недействительным; он может быть как a*n для некоторых n.

Answer 4

Внешняя петля не работает n/a раз, которая была бы с i + = a. Вместо этого он запускает журнал (a, n). Рассмотрим n = 30, a = 2.Это даст следующие действия:

рывок       я
                                        Так пятый раз он не будет выполняться. Это похоже на поведение log (2,30) (или log (30)/log (2)), которое возвращает около 4.906.

Итак, первый цикл работает 4 раза.

Теперь предположим, что вы хотите иметь этот внутренний цикл:

for(int j = 1; j <= i; j++) 

Это первый запустить 1 раз, потом 2 раза, затем 4 раза, затем 8 раз, затем 16 раз. Общее количество раз тогда:

1 + 2 + 4 + 8 + 16

который равен (2^m)*2-1, где m является log(2,30). В этом случае это будет 10, поэтому внутренний цикл будет работать 31 раз.

Теперь ваша внутренняя петля имеет i*b. Это означает, что он будет работать в два раза. Другими словами, ((2^m)*2-1)*b.

Таким образом, в общей сложности у нас есть:

int m = (int)Math.floor(log(a,n)); 
return ((a^m)*a-1)*b/(a-1); 

Это может быть сокращен до:

Return a^Math.floor(log(a,n))*b; 

Пожалуйста, поправьте меня, если я ошибаюсь, потому что я ничего не проверял. Был интересный вызов сделать из головы.