Qual a complexidade deste algoritmo

[LMV]

        long max = 1000;
        long soma = 0;
        long k = 0;
        for (long i = 0; i < N; i++) {
            if (i > max)
                max += 100;
           
            while (k < max) {
                soma++;
                k++;                
            }
        }

Não sei como fazer a análise temporal deste algoritmo. Alguém pode ajudar?

Edited November 30, 2020 at 03:17 PM by LMV
linha com print estava a mais

[maluco-123]

Boas

A mim parece-me O(N), tens aquele for loop até N.

O while loop dentro, depois das iniciais 1000 iterações (vindas do max), corre apenas 100 vezes a cada 100 iterações de i (vindas do if). O while loop, "esticado" para N->infinito, reduz-se a apenas uma iteração (soma++; k++;).

Com Ns baixos, < 1000, corre 1000 vezes (na primeira iteração de i), e depois não corre mais, ficando apenas dependente do for loop O(N).

Devo dizer que nunca fui muito bom nisto das complexidades, mas tenho ideia que a complexidade não é efectivamente o número absoluto de iterações, mas sim o "número médio" ou máximo de iterações para N.

 

Saúde

Edited November 30, 2020 at 01:10 AM by maluco-123
Complementar resposta