Big O Notation Homework - Código Fragmento análise de algoritmos? [fechadas]

Question

Para a lição de casa, me deram as seguintes 8 fragmentos de código para analisar e dar uma notação Big-Oh para o tempo de execução. Alguém pode por favor me diga se estou no caminho certo?

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

penso O (N) por um fragmento de

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O (N) para o fragmento de 2, bem

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O (N ^ 2) para o fragmento de 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O (N) para o fragmento de 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O (n ^ 2) para fragmento 5, mas o n * n é me jogando fora um pouco para que eu não tenho certeza

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O (N ^ 2) para o fragmento de 6, bem

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O (N ^ 3) para o fragmento de 7, mas mais uma vez o n * n é me jogando fora

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O (N) para o fragmento de 8

Answer 1

eu pensar fragmento 5 é O (n ^ 3), e de forma semelhante fragmento 7 é O (n ^ 5) *. Também parece que O (log (n)) para o fragmento de 8.

Para o n * n problemas, é necessário executar o corpo do loop n * n vezes, de modo que seria O (n ^ 2), então o composto que, com o fim do outro código. Fragmento 8 realmente duplica o contador ao invés de incrementá-lo, então quanto maior o problema, o trabalho menos adicional que você tem que fazer, por isso é O (log (n))

* edit: Fragmento 7 é O (n ^ 5), não O (n ^ 4), como eu pensava. Isto porque ambos j e k vão de 1 a n * n. Desculpe eu não entendi isso antes.

Answer 2

Fragmento 7 é O (n ^ 5), não O (n ^ 4) como o comentário reivindicações atualmente aceitos. Caso contrário, ele está correto.

Answer 3

Para o caso 8 tentar escrever o número de iterações para alguns valores de N e ver o que os olhares padrão como ... não é O (N)

Answer 4

Você parece estar no caminho certo. Com relação ao N * N o efeito que você acha que teria? É mais um fator de N por isso provavelmente seria uma ordem superior.

Apenas um aviso, vi outro post como este e foi extremamente baixo votado. Seja cuidadoso. Aqui é o post.

Answer 5

Você está no caminho certo, mas aqui vai uma dica de como as coisas podem ficar mais claras ao longo do caminho. Suponha que você tenha algum código:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

Right, considere o fato de que você tem o código em diferentes níveis. Neste exemplo, você só pode ver 3 níveis até agora:

1. O exterior para-ciclo que vai de 0-N
2. Outro para-loop que vai de 0-100
3. Alguns dentro do código, que está marcado como ...

Em nenhum momento você deve tentar calcular tudo em 1 lugar. Isto é onde a maioria dos iniciantes fazer algum tipo de erro aritmético. Calculá-lo individualmente para cada nível e, em seguida, multiplicá-lo todos juntos.

Boa sorte!