Ordem de Complexidade é um termo usado em ciência da computação para medir a eficiência de um algoritmo ou programa. Refere-se à quantidade de tempo e recursos necessários para resolver um problema ou executar uma tarefa. Na programação, a Ordem da Complexidade é geralmente expressa em termos de Grande O notação, que fornece um limite superior para os requisitos de tempo ou espaço de um algoritmo. Neste artigo, discutiremos a Ordem de Complexidade na linguagem de programação C e seu significado.
Ordem de complexidade na linguagem de programação C:
Na programação C, a Ordem de Complexidade de um algoritmo depende do número de operações realizadas pelo programa. Por exemplo, se tivermos um array de tamanho n e quisermos procurar um determinado elemento no array, a Ordem de Complexidade do algoritmo dependerá do número de elementos do array. Se realizarmos um Pesquisa Linear através do array, a Ordem de Complexidade será Sobre) , o que significa que o tempo necessário para procurar o elemento aumentará linearmente com o tamanho do array. Se usarmos um Algoritmo de pesquisa binária em vez disso, a Ordem da Complexidade será O (log n) , o que significa que o tempo necessário para procurar o elemento aumentará logaritmicamente com o tamanho do array.
Da mesma forma, a Ordem de Complexidade de outros algoritmos, como Algoritmos de classificação , Algoritmos Gráficos , e Algoritmos de Programação Dinâmica também depende do número de operações que o programa executa. A ordem de complexidade desses algoritmos pode ser expressa usando Grande O notação.
java concatenar strings
Vamos dar uma olhada em algumas ordens comuns de complexidade e seus algoritmos correspondentes:
Isso significa que o algoritmo leva um tempo constante, independentemente do tamanho da entrada. Por exemplo, acessar um elemento em um array leva O(1) tempo, pois o elemento pode ser acessado diretamente usando seu índice.
Isso significa que o tempo gasto pelo algoritmo aumenta logaritmicamente com o tamanho da entrada. Isto é comumente visto em Algoritmos de dividir e conquistar como Pesquisa binária , que dividem a entrada em partes menores para resolver o problema.
Isso significa que o tempo gasto pelo algoritmo aumenta linearmente com o tamanho da entrada. Exemplos de tais algoritmos são Pesquisa Linear e Tipo de bolha .
Isso significa que o tempo gasto pelo algoritmo aumenta em n multiplicado pelo logaritmo de n. Exemplos de tais algoritmos são Ordenação rápida e Mesclarsort .
Isso significa que o tempo gasto pelo algoritmo aumenta quadraticamente com o tamanho da entrada. Exemplos de tais algoritmos são Tipo de bolha e Classificação de inserção .
mapear iterador java
Isso significa que o tempo gasto pelo algoritmo dobra a cada aumento no tamanho da entrada. Isto é comumente visto em Algoritmos Recursivos como o Série Fibonacci .
É importante saber que a Ordem de Complexidade fornece apenas um limite superior para o tempo gasto pelo algoritmo. O tempo real gasto pode ser muito menor que esse limite, dependendo dos dados de entrada e da implementação do algoritmo.
Na programação C, a Ordem de Complexidade de um algoritmo pode ser determinada analisando o código e contando o número de operações realizadas. Por exemplo, se tivermos um loop que itera através de um array de tamanho n, a complexidade de tempo do loop será Sobre) . Da mesma forma, se tivermos uma função recursiva que se chama k vezes, a complexidade de tempo da função será O(2^k) .
Para otimizar o desempenho de um programa, é importante escolher algoritmos com menor Ordem de Complexidade. Por exemplo, se precisarmos classificar um array, devemos usar um algoritmo de classificação com uma ordem de complexidade mais baixa, como Ordenação rápida ou Mesclarsort , em vez de Tipo de bolha , que possui uma ordem de complexidade superior.
Analisando Ordem de Complexidade:
Para analisar a Ordem de Complexidade de um algoritmo, precisamos determinar como seu tempo de execução ou uso de espaço cresce à medida que o tamanho da entrada aumenta. O método mais comum para fazer isso é contar o número de operações básicas executadas pelo algoritmo.
sequência de comprimento
Uma operação básica é aquela que leva um tempo constante para ser executada, como adicionar dois números ou acessar um elemento de uma matriz. Contando o número de operações básicas realizadas pelo algoritmo em função do tamanho da entrada, podemos determinar sua Ordem de Complexidade.
Por exemplo, considere a seguinte função C que calcula a soma dos primeiros n inteiros:
Código C:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>