Horário de complexidade da impressão de números primos dentro de um intervalo?

Question

Eu escrevi uma resposta para este a pergunta, que pergunta sobre o seguinte:

Qual é o tempo de complexidade para o código que imprime números primos a partir de start para end?É $O(final*\sqrt{n})$?

/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

Aviso:Que não é o meu código.É por mahesh87.

Minha resposta para isso é:

---

No seu caso $n$ é end - start.No $O$ notação $n$ representa o tamanho de problema, que é o intervalo entre start e end em seu caso.No $O$ notação você está interessado, no pior dos casos, portanto, podemos assumir que start é sempre 0.Agora $n$ é apenas um alias para end.

Como temos definido $n$, é óbvio que printPrimeSeries é apenas $S(n)$ (a partir de 0 para end).O método usa findPrimeOrNot que itera de 2 para Math.sqrt(n), o que é $O(\sqrt{n})$.A combinação de ambos é $O(n)O(\sqrt{n})$, que é apenas $O(n\sqrt{n})$.

Observe que o $O$ notação diz algo sobre o comportamento assintótico do algoritmo.Não importa muito se existem 2 parâmetros, pelo menos neste caso.

Então, sim, sua suposição é totalmente correta (ignorando o que você escreveu end em vez de $n$).

---

Outros usuários têm proposto que a resposta correta é $O((end - start)\sqrt{end})$.Eu acho que este é um válido ponto de vista, mas ele não fornece qualquer informação benéfica em termos de $O$ notação para o caso específico.

Agora a minha pergunta:O que é o formalmente de maneira correta para descrever o tempo de complexidade de determinado algoritmo?É o meu raciocínio válido ou é simplesmente errado?

Answer 1

Tanto "o tempo de complexidade é $O( end \cdot \sqrt{end} )$"e "o tempo de complexidade é $O( (início-fim) \cdot \sqrt{end} )$"estão corretas afirmações (assumindo que as operações aritméticas sobre os envolvidos inteiros pode ser realizada em tempo constante).

O segundo limite superior é maior em alguns casos.Por exemplo, a definição $start=fim-de 10$, o primeiro superior permanece inalterado, enquanto o segundo simplifica para $O(\sqrt{end})$.

Observe, também, que "Em 𝑂 notação 𝑛 representa o tamanho de problema, que é o intervalo entre o início e o final em seu caso." é falsa.O tamanho do (razoável de codificação de) a instância é $O(\log final)$.

Answer 2

Sua função findPrimeOrNot(n) é executado em $O(n^{1/2})$ no pior caso.Muitas vezes, o tempo de execução é mais rápida.Por exemplo, para o mesmo número n, a função retorna depois de um único divisões.Mas para primos, onde todos os divisores de até sqrt(n) são testados, o tempo de execução é de fato $ heta(n^{1/2})$.E a chance de que um número inteiro aleatório x é primo é sobre x / log x.

Você teria que verificar o que exatamente o número médio de divisões é.Com seu algoritmo, o que pode ser melhorado, o número de divisões é, no mínimo, (end - start) * sqrt (n) / log n e, no máximo, cerca de (end - start) * sqrt (n) divisões.

Se você deseja imprimir o apronta, você vai descobrir que a impressão foi tão grande fator constante de que o tempo de execução da impressão sobre (end - start) / log n primos é muito maior do que o tempo para a impressão do apronto, para qualquer faixa razoável dos primes.