Число итераций в вложенных циклах?

Question

Так что я смотрел на этот код из учебника:

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

Автор заявил, что внутренние для цикла итерацию для точности N * (N-1)/2 раза, но не дает никаких оснований для того, как он прибыл к такому уравнению. Я понимаю N * (N-1), но зачем делиться на 2? Я сам запустил код и достаточно уверен, когда N равно 10, внутренний цикл повторяется 45 раз (10 * 9/2).

возился с кодом себя и попробовал следующее (назначается только я -j):

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

С N = 10, это приводит к 55. Так что у меня возникают проблемы с пониманием основной математики Вот. Конечно, я мог бы просто подключить все ценности и наложить свой путь через проблему, но я чувствую, что есть что-то существенное и очень простое, что мне не хватает. Как бы вы придумали уравнение для описания цикла for, который я только что построил? Есть ли способ сделать это, не полагаясь на выходы? Поблагодарите за помощь!

Answer 1

Подумайте, что происходит каждый раз, когда итерация внешнего цикла повторяется. В первый раз i == 0, поэтому внутренний цикл начинается с 1 и работает до N-1, что равно N-1 итераций. В следующий раз по внешнему контуру i увеличился до 1, поэтому внутренний цикл начинается с 2 и доходит до N-1, в общей сложности N-2 итераций. И этот шаблон продолжается: в третий раз по внешнему циклу вы получаете N-3 итераций, четвертый раз через, N-4 и т. Д. Когда вы дойдете до последней итерации внешнего цикла i == N-1, поэтому внутренний цикл начинается с j = N и останавливается немедленно. Итак, это нулевые итерации.

Общее число итераций сумма всех этих чисел:

(N-1) + (N-2) + (N-3) + ... + 1 + 0 

Чтобы посмотреть на это с другой стороны, это только сумма натуральных чисел от 1 до N-1. Результат этой суммы называется (N-1) th треугольным номером, а Wikipedia объясняет, как вы можете найти, что формула для n-го треугольного числа равна n (n + 1)/2. Но здесь у вас есть (N-1) -го треугольного числа, так что если вы установите n=N-1, вы получите

(N-1)(N-1+1)/2 = N(N-1)/2 

Answer 2

Посмотрите, сколько раз выполняется цикл внутреннего (j) для каждого значения i. Когда N = 10, внешний (i) цикл выполняется 10 раз, а j-цикл должен выполняться 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9 раз. Теперь вы просто добавляете эти числа, чтобы узнать, сколько раз выполняется внутренний цикл. Вы можете суммировать числа от 0 до N-1 с помощью формулы N (N-1)/2. Это очень незначительная модификация известной формулы для adding the numbers from 1 to N.

Для визуальной помощи, вы можете понять, почему 1 + 2 + 3 + ... + п = п * (п + 1)/2

Answer 3

Вы смотрите на вложенные петли, где внешний работает N раз, а внутренний (N-1). Вы фактически суммируете сумму 1 + 2 + 3 + ....

N * (N+1)/2 - «классическая» формула в математике. Молодой Карл Гаусс, позже известный математик, получил классную работу: добавив цифры от 1 до 100. Учитель ожидал, что дети будут заняты в течение часа, но Карл почти сразу ответил на вопрос: 5050. Он объяснил : 1 + 100; 2 + 99; 3 + 98; 4 + 97; и так далее до 50 + 51. Это 50 сум по 101 каждый. Вы также можете видеть, что как (100/2) * (100 + 1); вот откуда берет /2.

Что касается того, почему это (N-1), а не (N + 1), я упомянул ... что может иметь отношение к началу от 1, а не к 0, что приведет к отбрасыванию одной итерации из внутреннего цикла, I думать.

Answer 4

Если посчитать итерации внутреннего цикла, вы получите:

Чтобы получить общее для произвольного числа итераций, вы можете «обернуть» число примерно так:

0 1 2 3 4 
9 8 7 6 5 

Теперь, если мы добавим каждый из этих столбцов, то все dd до 9 (N-1), и есть 5 (N/2) столбцов. Совершенно очевидно, что для любого четного N мы все равно получаем N/2 столбца, каждый из которых добавляется до (N-1). Таким образом, когда общее число итераций четное, общее число итераций всегда (N/2) (N-1), которое (благодаря коммутативному свойству) можно переписать как N (N-1)/2.

Если бы мы сделали то же самое для нечетного числа итераций, у нас был бы один «нечетный» столбец, который нельзя было бы спарить. В этом случае мы можем игнорировать «0», так как мы знаем, что это не повлияет на общую сумму в любом случае. Например, рассмотрим N = 9 вместо N = 10. Для этого, мы получаем:

1 2 3 4 
8 7 6 5 

Это дает нам (N-1)/2 колонки (9-1 = 8, 8/2 = 4), что каждый добавить до N, так что сумма будет N * (N-1)/2. Несмотря на то, что мы пришли к этому несколько иначе, это точное соответствие для формулы выше, когда N равно. Опять же, кажется довольно очевидным, что это останется верным независимо от количества используемых столбцов (т. Е. Общего числа итераций).

Для любого N (нечетного или четного) сумма чисел от 0 до N-1 равна N * (N-1)/2.