Как рассчитать время работы алгоритма?

Question

В настоящее время я изучаю время выполнения Big O Notation.Я пытаюсь вычислить временную сложность некоторого кода:

int i = 1;
int n = 3;  //this variable is unknown
int j;

while (i<=n)
{
    for (j = 1; j < i; j++)
        printf_s("*");
    j *= 2;
    i *= 3;
}

Я думаю, что сложность этого кода равна О (log n).Но даже если это правильно, я не могу объяснить, почему.

Answer 1

Сложность по времени составляет , а не O (log n) , это O (n) .

.структурированный способ.Сначала мы рассмотрим внутренний цикл:

for (j = 1; j < i; j++)
    printf_s("*");

Здесь j повторяется от 1 до i.Таким образом, это означает, что для данного i потребуется i-1 шагов.

Теперь мы можем посмотреть на внешний цикл и абстрагировать внутренний цикл:

while (i<=n)
{
    // ... i-1 steps ...
    j *= 2;
    i *= 3;
}

Итак, на каждой итерации цикла while мы выполняем i-1 шагов.Кроме того, на каждой итерации i удваивается, пока не станет больше n.Таким образом, мы можем сказать, что число шагов этого алгоритма:

log3 n
---
\       k
/      3  - 1
---
k=0

Мы используем k в качестве дополнительной переменной, которая начинается с 0 и каждый раз увеличивается.Таким образом, он подсчитывает, сколько раз мы выполняем тело цикла while.Это закончится, когда 3^k > n, поэтому мы будем повторять лог ₃ ( n ) раз, и каждую итерацию внутренний цикл будет перезапускать в 3 ^k -1 шагов.

Приведенная выше сумма эквивалентна:

          log3 n
           ---
           \       k
-log3 n +  /      3
           ---
           k=0

Выше приведена геометрическая серия [wiki] , что равно: (1-3 ^{log ₃ n} ) / (1-3) , или упрощенно, оно равно (n ^{log ₃ 3} -1) / 2 и, следовательно, (n-1) / 2 .

Итогоколичество шагов, таким образом, ограничено: (n-1) / 2 - log ₃ n или сформулировано проще O (n) .

Answer 2

Тело внутреннего цикла будет выполнено 1, 3, 9, 27, ..., 3 ^ k раз, где k = ceil (log ₃ (n)).

Здесь мы можем использовать тот факт, что Σ _{0 <= i <k} 3 ⁱ <= 3 <sup>k . Это можно доказать по индукции.</sub>

Таким образом, мы можем сказать, что внутренний цикл выполняется не более 2 * 3 ^ k раз, где 3 ^ k <3n, который является линейным по n, а именно <code>O(n).

Answer 3

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

---

Иногда, если вы плохо разбираетесь в математике, вы все равно можете найти число с помощью экспериментов.Алгоритм, скомпилированный с -O3, довольно быстро тестируется с различными n.Я заменил printf_s простым приращением к счетчику, который затем возвращается из функции, и использую unsigned long long в качестве типа.С этими изменениями мы получаем

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <inttypes.h>

unsigned long long alg(unsigned long long n) {
   unsigned long long rv = 0;
   unsigned long long i = 1;
   unsigned long long j;

   while (i <= n) {
       for (j = 1; j < i; j++)
           rv += 1;

       i *= 3;
   }
   return rv;
}

int main(void) {
    unsigned long long n = 1;
    for (n = 1; n <= ULONG_MAX / 10; n *= 10) {
        unsigned long long res = alg(n);
        printf("%llu %llu %f\n", n, res, res/(double)n);
    }
}

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

1 0 0.000000
10 10 1.000000
100 116 1.160000
1000 1086 1.086000
10000 9832 0.983200
100000 88562 0.885620
1000000 797148 0.797148
10000000 7174438 0.717444
100000000 64570064 0.645701
1000000000 581130714 0.581131
10000000000 5230176580 0.523018
100000000000 141214768216 1.412148
1000000000000 1270932914138 1.270933
10000000000000 11438396227452 1.143840
100000000000000 102945566047294 1.029456
1000000000000000 926510094425888 0.926510
10000000000000000 8338590849833250 0.833859
100000000000000000 75047317648499524 0.750473
1000000000000000000 675425858836496006 0.675426

. Отсюда видно, что отношение числа отпечатков к n на самом деле не сходится, но кажется, что оно очень сильно ограничено константами с обеих сторон, поэтому O(п).