Determinar a eficiência de um algoritmo envolve analisar sua complexidade de tempo e complexidade do espaço . Isso nos ajuda a entender como o uso de recursos do algoritmo (tempo e memória) escala com o tamanho da entrada. Aqui está um colapso do procedimento de computação:

1. Entenda a complexidade do tempo e a complexidade do espaço:

* complexidade do tempo: Mede a quantidade de tempo que um algoritmo leva para concluir em função do tamanho da entrada (geralmente indicado como 'n'). Estamos interessados ​​em * como o tempo de execução cresce, não o tempo exato em segundos.

* Complexidade do espaço: Mede a quantidade de memória (ou espaço) que um algoritmo requer em função do tamanho da entrada 'n'. Isso inclui o espaço para dados de entrada e quaisquer estruturas de dados auxiliares usadas pelo algoritmo.

2. Identificando operações -chave:

* Operações básicas: Identifique as operações que contribuem significativamente para o tempo de execução. Estes podem incluir:
* Operações aritméticas (+, -, \*, /, %)
* Comparações (<,>, ==,! =)
* Atribuições (=)
* Acesso à matriz (arr [i])
* Alocações e desalocações de memória (dependendo do idioma)

* Concentre -se nas operações dominantes: Algumas operações serão executadas com muito mais frequência do que outras. Concentre -se nessas operações * dominantes *, pois elas terão o maior impacto no tempo de execução geral. Por exemplo, em um algoritmo de classificação, comparações e swaps são dominantes.

3. Analise a estrutura do algoritmo (passo a passo do código):

* Declarações seqüenciais: As declarações executadas em sequência contribuem com uma quantidade constante de tempo ou espaço.

* Loops: A complexidade do tempo de um loop depende de quantas vezes ele itera:
* Loop simples (linear): `Para i no intervalo (n):...` executa 'n' vezes, então a complexidade é O (n).
* loops aninhados (quadrático, cúbico, etc.): `Para i no intervalo (n):para j no intervalo (n):...` executa 'n * n' vezes, então a complexidade é O (n^2).
* loop com comportamento logarítmico: `enquanto n> 1:n =n // 2` executa o log2 (n) vezes, então a complexidade é O (log n).
* loop com dependência da lógica interna: Analise o corpo do loop para determinar sua complexidade e multiplicá -lo pelo número de iterações.

* declarações condicionais (se/else):
* Analise os blocos `if` e` else`. A complexidade geral é o * máximo * das complexidades dos blocos `if` e` else`.
* Para estruturas profundamente aninhadas `if/else`, rastrear cuidadosamente os possíveis caminhos de execução.

* Recursão:
* Identifique os casos base: Estes encerram a recursão.
* Identifique a etapa recursiva: Como o problema é dividido em subproblemas menores.
* Escreva uma relação de recorrência: Isso descreve matematicamente a complexidade do tempo da função recursiva. Por exemplo:`t (n) =t (n/2) + o (1)` (pesquisa binária)
* Resolva a relação de recorrência: Use métodos como o teorema mestre, substituição ou árvore de recursão para encontrar a complexidade do tempo assintótico.

* Chamadas de função: Considere a complexidade do tempo da função chamada. Se uma função `a` chama função` b`, a complexidade do tempo de `a` incluirá a complexidade do tempo de` b '.

4. Expresse complexidade na notação assintótica (Big O, grande ômega, grande teta):

* NOTAÇÃO OBSERENDA O (O): Representa o * limite superior * da taxa de crescimento do algoritmo. Ele descreve o cenário * pior dos casos *. "A complexidade do tempo do algoritmo é O (n^2)" significa que o tempo de execução do algoritmo não crescerá * mais rápido * do que n^2 como 'n' aumenta.

* Notação ômega grande (ω): Representa o limite * inferior * da taxa de crescimento do algoritmo. Ele descreve o cenário * Best Case *. "A complexidade do tempo do algoritmo é ω (n)" significa que o tempo de execução do algoritmo não crescerá * mais lento * do que 'n' como 'n' aumenta.

* Notação Big Theta (θ): Representa o * limite apertado * da taxa de crescimento do algoritmo. Ele descreve o cenário de caso médio e quando o tempo de execução do algoritmo cresce na mesma taxa que a função. "A complexidade do tempo do algoritmo é θ (n log n)" significa que o tempo de execução do algoritmo crescerá na mesma taxa que n log n.

complexidades de tempo comuns (pior caso, grande o):

* o (1):tempo constante: O tempo de execução é independente do tamanho da entrada. Exemplo:acessar um elemento em uma matriz pelo seu índice.
* o (log n):tempo logarítmico: O tempo de execução aumenta logaritmicamente com o tamanho da entrada. Exemplo:pesquisa binária em uma matriz classificada.
* o (n):tempo linear: O tempo de execução aumenta linearmente com o tamanho da entrada. Exemplo:pesquisando um elemento em uma matriz não classificada.
* o (n log n):tempo linearítmico: Comum em algoritmos de classificação eficientes. Exemplo:Mesclar classificar, Quicksort (caso médio).
* o (n^2):tempo quadrático: O tempo de execução aumenta quadraticamente com o tamanho da entrada. Exemplo:classificação de bolhas, classificação de inserção.
* o (n^3):Tempo cúbico: Exemplo:multiplicação da matriz.
* o (2^n):tempo exponencial: O tempo de execução dobra com cada adição ao tamanho da entrada. Geralmente indica uma abordagem de força bruta. Exemplo:tentando todos os subconjuntos possíveis de um conjunto.
* o (n!):Tempo fatorial: O tempo de execução cresce extremamente rapidamente. Exemplo:encontrando todas as permutações de um conjunto.

5. Ignore fatores constantes e termos de ordem inferior:

Ao usar notação assintótica, estamos principalmente interessados ​​no termo * dominante * que determina a taxa de crescimento. Fatores constantes e termos de ordem inferior tornam-se insignificantes à medida que 'n' cresce muito grande.

* `3n^2 + 5n + 10` é simplificado para` o (n^2) `
* `100 log n + n` é simplificado para` o (n) `(n cresce mais rápido que o log n)
* `2^n + n^5` é simplificado para` o (2^n) `

6. Analise a complexidade do espaço:

Semelhante à complexidade do tempo, analise o espaço usado pelo algoritmo. Considerar:

* Espaço de entrada: O espaço necessário para armazenar os dados de entrada.
* Espaço auxiliar: O espaço extra usado pelo algoritmo, além do espaço de entrada, para variáveis, estruturas de dados e pilha de chamadas de recursão.

Exemplos:

* Pesquisa linear:

`` `Python
def linear_search (arr, alvo):
para i em range (len (arr)):
Se arr [i] ==Target:
retornar i
retornar -1
`` `

* complexidade do tempo: O (n) (linear, pior caso:o alvo não está na matriz ou é o último elemento)
* Complexidade do espaço: O (1) (constante, porque usa apenas algumas variáveis ​​extras)

* Pesquisa binária:

`` `Python
def binary_search (arr, destino):
baixo =0
High =Len (arr) - 1
enquanto baixo <=alto:
MID =(baixo + alto) // 2
Se arr [mid] ==Target:
retornar meio
Elif arr [Mid] baixo =meio + 1
outro:
High =Mid - 1
retornar -1
`` `

* complexidade do tempo: O (log n) (logarítmico)
* Complexidade do espaço: O (1) (versão iterativa constante)

* Pesquisa binária recursiva:

`` `Python
def binary_search_recursive (arr, alvo, baixo, alto):
Se baixo> alto:
retornar -1
MID =(baixo + alto) // 2
Se arr [mid] ==Target:
retornar meio
Elif arr [Mid] Retornar binário_search_recursive (arr, alvo, médio + 1, alto)
outro:
Retornar binário_search_recursive (arr, alvo, baixo, meados - 1)
`` `

* complexidade do tempo: O (log n)
* Complexidade do espaço: O (log n) devido à profundidade da recursão. Cada chamada recursiva adiciona um novo quadro à pilha de chamadas.

em resumo:

1. Defina o que você deseja medir: Complexidade do tempo, complexidade do espaço ou ambos.
2. Identifique as operações principais contribuindo para o uso de recursos.
3. Analise a estrutura do algoritmo (loops, condicionais, recursão).
4. expressar a complexidade Usando Big O, Big Omega ou grande notação teta.
5. Ignore fatores constantes e termos de ordem inferior.

Seguindo essas etapas, você pode analisar efetivamente a eficiência dos algoritmos e escolher o algoritmo mais adequado para suas necessidades específicas. Lembre -se de que o melhor algoritmo depende do problema específico, do tamanho dos dados de entrada e dos recursos disponíveis.