Измерение производительности для петли без н - PullRequest
Новая
       25

Измерение производительности для петли без н

0 голосов
/ 31 декабря 2018

Мне интересно, какова сложность цикла for, который повторяется каждый раз, когда он вызывается от 1 до 10, вне зависимости от ввода.

Вот пример - n является вводом: 

int count = 0;
int max = n + 1;

for (int a = 1; a < max; a++)
{
   for (int b = 1; b < a; b++)
   {
     for (int c = 1; c < 10; c++)
     {
      count = count + 1
     }
   }
}
return count

Итак, я подумал, что сложность внутреннего цикла for равна 1, а другой равен каждому n + 1?=> 1 + 1 + (n + 1) (1+ (n + 1) (1 + 1 + 1)) + 1 = 3n² + 7n + 7

или это10 из-за десяти итераций?=> 1 + 1 + (n + 1) (1+ (n + 1) (1 + 10 + 10)) + 1 = 21n² + 43n + 25

Так что в основном послеоставляя константы в стороне, это сложность O (n²)

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

Спасибо,

Поздравляю с Новым годом

1 Ответ

0 голосов
/ 02 января 2019

Если ваш цикл всегда выполняется фиксированное количество раз, это не влияет на сложность, потому что вы можете «развернуть» его: 

for (int a = 1; a < max; a++)
{
    for (int b = 1; b < a; b++)
    {
        count = count + 1  // c = 1
        count = count + 1  // c = 2
        count = count + 1  // c = 3
        count = count + 1  // c = 4
        count = count + 1  // c = 5
        count = count + 1  // c = 6
        count = count + 1  // c = 7
        count = count + 1  // c = 8
        count = count + 1  // c = 9
    }
}

Программа, которую вы получаете, имеет точно такую ​​же семантику, что ипервая и та же большая сложность O.

À offer

"Развертывание цикла" - одна из оптимизаций, используемых компиляторами C / C ++.Например, в GCC вы включаете его с флагом -funroll-loops.

-funroll-loops

Разверните циклы, количество итераций которых можно определить во время компиляцииили при входе в цикл.-funroll-loops подразумевает -frerun-cse-after-loop.Эта опция увеличивает код и может или не может заставить его работать быстрее.

source: https://gcc.gnu.org/onlinedocs/gcc-4.5.2/gcc/Optimize-Options.html

...