A complexidade do tempo de execução de um loop `while` depende inteiramente de quantas vezes o loop itera. Não há resposta única e definitiva. É crucial analisar a condição que controla o loop e como as variáveis ​​envolvidas nessa condição mudam dentro do loop.

Aqui está um colapso de cenários comuns e suas complexidades de tempo de execução:

1. Tempo constante (O (1))

* Quando o loop executa um número fixo e pequeno de vezes, independentemente do tamanho da entrada. Isso é raro, mas pode acontecer se a condição do loop depende de um valor constante e não for afetado pela entrada.

`` `Python
i =0
Enquanto eu <5:# loops exatamente 5 vezes
impressão (i)
i +=1
`` `

2. Tempo logarítmico (O (log n))

* Quando o loop reduz o tamanho do problema por um fator constante em cada iteração. Um exemplo clássico é a pesquisa binária.

`` `Python
baixo =0
alto =n - 1
enquanto baixo <=alto:# loop continua enquanto o espaço de pesquisa existir
MID =(baixo + alto) // 2
Se arr [mid] baixo =meio + 1
Elif arr [MID]> Target:
High =Mid - 1
outro:
Retorne Mid # Target Encontrado!
`` `

Aqui, o tamanho do espaço de pesquisa (de `baixo 'a` high') é aproximadamente metade em cada iteração. Portanto, o loop é executado aproximadamente `log2 (n)` times.

3. Tempo linear (O (n))

* Quando o loop itera através de cada elemento de uma entrada de tamanho `n` uma vez. Isso é muito comum.

`` `Python
i =0
enquanto eu Imprima (arr [i]) # acessando cada elemento de 'arr' uma vez.
i +=1
`` `

Nesse caso, o corpo do loop é executado `n 'Times.

4. Tempo quadrático (O (n^2))

* Quando o loop itera `n` vezes para cada um dos elementos` n` (geralmente aninhados).

`` `Python
i =0
Enquanto eu j =0
enquanto j impressão (i, j)
j +=1
i +=1
`` `

Isso envolve um loop aninhado `while ', onde ambos os loops iteram` n` vezes. O número total de iterações é `n * n =n^2`.

5. Outro tempo polinomial (O (n^k))

* Generalizações do exemplo quadrático acima. Por exemplo, três loops aninhados que cada um `n` tempos resultaria em complexidade O (n^3).

6. Tempo exponencial (O (2^n)) ou pior

* O tempo de execução do loop cresce exponencialmente com o tamanho da entrada. Isso geralmente indica um algoritmo mal projetado ou um problema inerentemente muito difícil. Exemplos podem envolver a tentativa de todas as combinações possíveis de elementos.

Considerações importantes:

* Tamanho da entrada (n): O que `n` representa? O tamanho de uma matriz, a magnitude de um número, etc. Isso é fundamental para expressar a complexidade em termos de entrada.
* Alterações variáveis ​​da condição: Como as variáveis ​​que controlam a condição de loop muda dentro do loop? Aumenta em uma quantidade constante, diminui em um fator etc.?
* operações dentro do loop: O tempo de execução das operações * dentro * do loop é importante. Se, por exemplo, você tiver uma operação O (n) dentro de um loop que roda n vezes, a complexidade geral é O (n * n) =O (n^2).

Como determinar a complexidade do tempo de execução:

1. Identifique o tamanho da entrada (n): Qual é o parâmetro de tamanho relevante?
2. Determine o número de iterações: Quantas vezes o loop é executado *em relação a `n` *? Esta é a parte principal.
3. Considere operações dentro do loop: Se o loop contiver operações complexas, sua complexidade de tempo de execução deve ser levada em consideração. A complexidade geral se torna a complexidade das iterações de loop multiplicadas pela complexidade da operação mais cara dentro do loop.
4. expressar a complexidade: Use grande notação O (O (), ω (), θ ()) para representar o limite superior, o limite inferior ou o limite apertado do tempo de execução. Normalmente, nos concentramos em Big O (pior cenário).

Exemplo:

`` `Python
DEF Process_array (arr):
n =len (arr)
i =0
Enquanto eu j =i + 1
enquanto j Se arr [i]> arr [j]:
arr [i], arr [j] =arr [j], arr [i] # troca de tempo constante
j +=1
i +=1
retornar arr
`` `

Análise:

* `n` é o comprimento da matriz de entrada` arr`.
* O loop externo (`i`) é executado` n` times.
* O loop interno (`j`) é executado aproximadamente` n - i` times. Na pior das hipóteses, quando `i` é 0, ele é executado 'n'.
* A operação de troca dentro do loop interno é O (1).

Portanto, os loops aninhados contribuem para a complexidade de O (n^2). A troca é tempo constante e não afeta o tempo de execução geral do O (n^2). Esse algoritmo é semelhante ao tipo de seleção.
Em resumo, para determinar a complexidade do tempo de execução de um loop `while`, analise cuidadosamente quantas vezes o loop é executado em relação ao tamanho da entrada e considere a complexidade das operações realizadas dentro do loop.