problemas da ciência da computação , muitas vezes envolvem mais de uma solução , e cada solução é alcançada seguindo um conjunto de regras , também conhecido como um algoritmo. Notação O grande fornece um método de descrever a eficiência de um algoritmo - por outras palavras , o tempo que leva para que um algoritmo de correr como uma função do tamanho da entrada para esse algoritmo . Background Fotografia de

Big O notação - também conhecido como símbolo de Landau, em homenagem ao matemático judeu alemão, Edmund Landau - descreve a taxa de crescimento de uma função , também conhecido como a sua " ordem", daí a letra maiúscula "O" Big O notação é concebido para medir o desempenho de um algoritmo em si , ao invés do hardware no qual o algoritmo é executado. Um pedaço de hardware pode ser mais rápido ou mais lento do que o outro por um fator constante, para que todos os fatores constantes são removidos Big O notação .
Tempo Constante

Um algoritmo que sempre leva aproximadamente o mesmo tempo de funcionamento, independentemente do tamanho da entrada , diz-se que o tempo de marcha " constante " . Em notação Big O , este tipo de algoritmo é um algoritmo conhecido como " ordem de 1 " e é designada por O ( 1 ) . Exemplos de O (1) algoritmos incluem empurrando ou popping dados de e para uma pilha de programação , e recuperar um único item de dados a partir de uma matriz quando você sabe que a sua posição. Esses algoritmos apenas realizar um certo número de passos, não importa quão grande a entrada se torna.
Linear Tempo

Um algoritmo cuja execução tempo aumenta proporcionalmente Correr, ou de um modo linear , com o tamanho da sua entrada é dito ter " linear " tempo de execução . Em notação Big O , este tipo de algoritmo é conhecido como uma " ordem n " algoritmo e é indicado por S ( n ) , o que indica que o tempo que leva para que o algoritmo para executar aumenta linearmente com o número de itens de dados ", n , " aumenta. Um exemplo simples de um S ( n ) algoritmo é um algoritmo que calcula o total de uma lista de números ; uma adição é necessária para cada um dos elementos na lista , de modo que o número de adições é o mesmo que o número de elementos < br . >
Tempo de duração quadrática

um algoritmo cuja execução tempo aumenta por um fator de n ^ 2 , quando o tamanho dos seus aumentos de entrada por um fator de " n" é dito ter " quadrática " correr do tempo. Em notação Big O , este tipo de algoritmo é conhecido como um fim n ^ 2 algoritmo , ou simplesmente um algoritmo quadrática , e é designado por O (n ^ 2 ) . Exemplos de O ( n ^ 2 ) algoritmos incluem algoritmos de ordenação , tais como tipo de inserção e bubble sort , em que dobrando o tamanho da entrada quádruplos o tempo de execução .