#c #algorithm #performance #big-o
#c #алгоритм #Производительность #big-o
Вопрос:
У меня здесь есть функция, которую я вижу, это O (N ^ 2). Тем не менее, я пытаюсь точно определить, сколько шагов / вычислений использует каждая строка.
void hi(int n){
for (int i=1; i <= n; i ) { //line 1
for (int k = i; k <= n; k ) { //line 2
puts("hi"); //line 3
}
}
}
Для строки 1 я считаю, что это 1 (N 1) 1.
Строки 2 и 3 предположительно являются суммой (i = от 1 до n) (3i 2), но я не понимаю, как это сделать. Откуда взялось это суммирование?
Ответ №1:
Внешняя for инструкция выполняется один раз … хотя это повторяется n несколько раз (из-за начального условия, конечного условия и частей обновления). Это «строка 1».
Внутренний for оператор будет выполняться один раз для каждой итерации внешнего цикла. Внешний цикл повторяется n несколько раз, поэтому внутренний for оператор выполняется n несколько раз. Это «строка 2».
"hi" будет записываться один раз для каждой итерации внутреннего цикла. Внутренний цикл будет повторять n-i 1 время для каждой итерации внешнего цикла (который выдает значение i ). Это означает, что количество раз "hi" , которое печатается, равно n (для i == 1 ) n-1 (для i == 2 ) …. 1 (для i==n ). Суммируя их, это приравнивается к n*(n 1)/2 временам. Это «строка 3».
Комментарии:
1. Я должен включать инициализатор, условие и приращения циклов for . Поскольку строка 1 выполняется только один раз, это должно быть просто 1 (N 1) 1. Для второй строки, поскольку она выполняется N раз, означает ли это, что общее количество шагов будет равно N * (1 (N 1) 1), поскольку весь цикл for сбрасывается для каждого N?
2. Вы упускаете из виду тот факт, что переменная, управляющая внешним циклом, также управляет количеством итераций внутреннего цикла.
Ответ №2:
Строка 1 выполняется 1 раз. Однако он выполняет 1 инициализацию, n сравнений и приращений.
Строка 2 выполняется n раз. Однако он выполняет n инициализаций, n*(n 1)/2 сравнений и приращений.
Строка 3 выполняется n*(n 1)/2 раза. Из-за http://mathcentral.uregina.ca/qq/database/qq.02.06/jo1.html
Таким образом, общее количество операций равно 1 3n 3n *(n 1) / 2.
Комментарии:
1. Почему строка 1 выполняется один раз??
2. Обычно вы подсчитываете for-элемент, а не приращение, поэтому for выполняется только 1 раз при каждом вызове hi .
3. Я должен включать все части цикла for. Будет ли строка 2 тогда N * (1 (N 1) 1)?
4. Нет, все именно так, как указано. Наибольшее внутреннее значение определит вашу нотацию Big-O, которая, как вы сами заявили, равна O (n ^ 2). Общее количество выполненных операций равно сумме строк (1) (n) (n*(n 1)/2).
5. Верно, но я думаю, что мы рассматриваем разные уровни детализации. Например, вы упомянули, что обычно вы считаете цикл for только как один, но в моем случае я должен также включить инициализацию, проверку условий и приращение, поэтому у меня есть 1 (n 1) 1.