Истерирование вложенной петли

Question

Извините, если я повторно задаю предыдущий вопрос, но я не могу найти конкретный ответ на этот вопрос. Как я могу сделать формулу для вложенного для итераций цикла, кроме основных, таких как:

for (int i =0; i < N; i++) 

Я получаю основную концепцию количества итераций основных циклов:

for (int i =0; i < N; i++) 

Булево условие равно некоторые переменные (например, N), то вычитается из начальной переменной (например, i), а затем делится на число вложенных циклов (в этом случае 1, так как оно не вложено). Таким образом, число итераций для этого цикла будет:

(N - i)/1 

Например, для нахождения итераций вложенных циклов это будет повторяться вниз петля, пока вы не сделаете его внутренний цикл, то вы несколько всех петель для счетчик итераций.

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

for (int i = 1; i < 1000; i *= 2) 
    for (int j = 0; j < 1000; j++) 

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

Answer 1

Просто выработайте, сколько раз каждый цикл. Это легко, потому что они не являются взаимозависимыми (т.е.j цикл не полагается на i).

• Цикл i идет 1, 2, 4, 8, 16, ..., 512. Так как он должен быть меньше 1000, он остановится, когда достигнет 1024. Это всего 10 итераций. Подсчитайте их вручную или вычислите log2(1024).

• Провод j0, 1, 2, 3, ..., 999. Это всего 1000 итераций.

Таким образом, у вас есть внутренняя петля из 1000 итераций, которая повторяется 10 раз внешним контуром. Это всего 10 000 итераций.

Answer 2

Я думаю, что вы читаете синтаксис цикла неправильно?

Попробуйте читать их вслух, как это:

для этого цикла:

for (int i = 1; i < 1000; i *= 2) 

Синтаксис цикла читает:

начиная с одного, держать цикл в то время как я меньше, чем один тысячи - и каждый раз вокруг цикла умножайте i на два.

Итак, я начинаю с одного и получает умноженное на два каждый раз вокруг цикла - то есть 1, 2, 4, 8, 16 .... Это продолжается до тех пор, пока оно не достигнет тысячи (или более он) - и цикл останавливается.

и для этого цикла:

for (int j = 0; j < 1000; j++) 

синтаксис цикла говорит:

Начиная с нуля, держать цикл в то время как J меньше, чем одна тысяча - и каждый раз вокруг петли, добавьте к j.

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

Я считаю, что чтение вещей вслух - или озвучивание их в голове - может действительно помочь понять их.