Как посчитать время выполнения алгоритма с расширяющимся массивом (который сам зацикливается) внутри цикла? - PullRequest
Новая
       6

Как посчитать время выполнения алгоритма с расширяющимся массивом (который сам зацикливается) внутри цикла?

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

У меня есть алгоритм для нахождения списка простых чисел под N, а также наименьшего коэффициента всех чисел N. 

/*
arrLF stands for arrLowestFactor, it stores all the LF
arrPrime is the list of primes under N. The variable pn is used to keep track of how many primes we have discovered. Initially pn is zero.
*/
for(int i = 2; i <= N; i++){
     //if a number i hasn't got its lowest factor yet, it means we have discovered a new prime number. And this prime number will be the LF of i too.
    if(!arrLF[i]){
        arrPrime[pn++] = i;
        arrLF[i] = i;
    } 

    //run through the list of prime once and fill up the lowest factor of (i * arrPrime[j]) in the arrLF table 
    //it's like doing sieve of eratosthenes but we build the table up one at a time
    for(int j = 1; i * arrPrime[j] <= N; j++){
        arrLF[ i * arrPrime[j] ] = arrPrime[j];
        if( i % arrPrime[j] == 0)
            break;
    }
}

Длявнешний цикл, он работает на O (N).Таким образом, выполнение этого алгоритма будет O (N * M), где M - время выполнения внутреннего цикла.Но так как список простых чисел постоянно расширяется, как я могу оценить сложность M?

Кстати, я нашел этот алгоритм, изучая решение красного кодера на codeforce, кто-нибудь знает этот алгоритм или его имя?

1 Ответ

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

ваш алгоритм будет работать в O (n).Позвольте мне объяснить, почему

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

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

1-я итерация: 1/2 * N раз

2-я итерация: 1/3 * N раз

3-я итерация: 1/4 * N раз

и т. Д.

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

, и мы можем сказать общее количество раз, которое внутренний циклбудет работать SUM (1/2 + 1/3 + 1/4 + ... 1 / N)

, и это называется гармоническим рядом https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

, и хотя этот ряд сходитсядо бесконечности, это очень медленно сходится, что для N 10 ^ 43 это меньше, чем 100

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

Это означает, что временная сложность полного алгоритма равнавыход внутреннего цикла, потому что внешний цикл не запускает никаких других циклов.Таким образом, временная сложность будет равна O (Xn), где X - это постоянное число, которое, как мы объяснили, реально не превысит 100 или 200 в пределах чисел java, что будет означать, что общая сложность алгоритма равна O (n), так как мы опускаемпостоянная

...