[Powered by Google Translate] Você provavelmente já ouviu pessoas falarem sobre um algoritmo rápido e eficiente para a execução de sua tarefa particular, mas o que exatamente significa isso para um algoritmo para ser rápido ou eficiente? Bem, ele não está falando de uma medição em tempo real, como segundos ou minutos. Isto é porque o hardware do computador e programa pode variar drasticamente. Meu programa pode ficar mais lento do que o seu, porque eu estou correndo em um computador antigo, ou porque eu acontecer de estar jogando um jogo online ao mesmo tempo, que se toda a memória hogging meu, ou eu poderia estar rodando meu programa através de um software diferente que comunica com o aparelho de forma diferente a um nível baixo. É como comparar maçãs e laranjas. Só porque o meu computador mais lento demora mais do que a sua para dar de volta uma resposta não significa que você tem o mais eficiente. 

Então, já que não podemos comparar diretamente os tempos de execução de programas em segundos ou minutos, como podemos comparar dois algoritmos diferentes independentemente do seu hardware ou ambiente de software? Para criar uma maneira mais uniforme da medição da eficiência algorítmica, cientistas da computação e matemáticos desenvolveram conceitos para a medição da complexidade assintótica de um programa e uma notação chamada 'Ohnotation Big' para descrever este. A definição formal é que uma função f (x) é executado no fim de g (x) se existir um certo valor (x), x e ₀ uma constante, C, para o qual f (x) é menor do que ou igual a que constante vezes g (x) para todo x maior que x ₀. 

Mas não se espantam com a definição formal. O que isso realmente significa em termos menos teóricas? Bem, é basicamente uma forma de analisar quão rápido tempo de execução de um programa cresce assintoticamente. Ou seja, como o tamanho de seus insumos aumenta em direção ao infinito, digamos, está uma matriz de classificação de tamanho 1000 em comparação com uma matriz de tamanho 10. Como o tempo de execução do seu programa de crescer? Por exemplo, imagine contagem do número de caracteres em uma corda a maneira mais simples  andando por toda a cadeia letra por letra e adicionando um a um contador para cada personagem. Este algoritmo é dito para ser executado em tempo linear no que diz respeito ao número de caracteres, 'N' na cadeia. Em suma, ele é executado em O (n). Por que isso? Assim, utilizar esta abordagem, o tempo necessário para atravessar toda a cadeia é proporcional ao número de caracteres. Contando o número de caracteres em uma seqüência de 20 caracteres vai ter o dobro do tempo que for preciso para contar os caracteres em uma seqüência de 10 caracteres, porque você tem que olhar para todos os personagens e cada personagem tem a mesma quantidade de tempo para olhar. À medida que aumenta o número de caracteres, o tempo de execução irá aumentar linearmente com o tempo de entrada. 

Agora, imagine se você decidir que o tempo linear, O (n), mas não foi rápido o suficiente para você? Talvez você está armazenando grandes seqüências, e você não pode pagar o tempo extra que seria necessário para percorrer todos os seus caracteres de contagem um-por-um. Então, você decide tentar algo diferente. E se você acontecer para já armazenar o número de caracteres na seqüência, digamos, em uma variável chamada 'len' no início do programa, antes mesmo armazenado o primeiro personagem na sua corda? Então, tudo o que você tem que fazer agora para descobrir o comprimento da corda, é verificar que o valor da variável. Você não tem que olhar para a própria string, em tudo, e aceder ao valor de uma variável como len é considerado uma operação de tempo constante assintoticamente, ou O (1). Por que isso? Bem, lembre-se que a complexidade assintótica significa. O que muda no tempo de execução como o tamanho de seus insumos cresce? 

Diga que você estava tentando obter o número de caracteres em uma seqüência maior. Bem, não importa o quão grande você fazer a seqüência, até um milhão de caracteres, tudo o que você tem que fazer para encontrar o comprimento da corda com esta abordagem, é a leitura do valor da variável de len, que você já fez. O comprimento de entrada, isto é, o comprimento da corda que você está tentando encontrar, não afeta a todos o quão rápido o programa é executado. Esta parte do seu programa seria executado igualmente rápido em uma cadeia de um caractere e uma seqüência de mil caracteres, e é por isso que este programa seria referido como sendo executado em tempo constante com respeito ao tamanho de entrada. 

Claro, há uma desvantagem. Você gasta espaço de memória extra no seu computador armazenar a variável e o tempo extra que você leva para fazer o armazenamento real da variável, mas o ponto ainda está de pé, descobrir quanto tempo sua seqüência foi não depende do comprimento da corda em tudo. Então, ele é executado em O (1) ou de tempo constante. Isto certamente não tem de significar que o código é executado em uma etapa, mas não importa quantos passos é, se não se altera com o tamanho das entradas, ainda é assintoticamente constante que representamos com O (1). 

Como você provavelmente pode adivinhar, existem vários grandes runtimes O para medir com algoritmos. O (n) ² algoritmos são assintoticamente mais lento do que O (n) algoritmos. Isto é, como o número de elementos (n) aumenta, eventualmente, O (n) ² algoritmos vai levar mais tempo que O (n) para executar algoritmos. Isso não significa que O (n) algoritmos sempre correr mais rápido do que O (n) ² algoritmos, mesmo no mesmo ambiente, no mesmo hardware. Talvez para pequenos tamanhos de entrada,  O (n) ² algoritmo pode realmente trabalhar mais rápido, mas, eventualmente, tal como o tamanho de entrada aumenta para o infinito, a O (n) tempo de execução ² algoritmo acabará por eclipsar o tempo de execução do algoritmo O (n). Assim como qualquer função quadrática matemática  eventualmente ultrapassar qualquer função linear, não importa o quanto de uma cabeça de iniciar a função linear começa com. Se você estiver trabalhando com grandes quantidades de dados, algoritmos que são executados em O (n) ² pode realmente acabar retardando o seu programa, mas para tamanhos de entrada pequenas, você provavelmente não vai nem perceber. 

Outra complexidade assintótica é, tempo logarítmica, O (log n). Um exemplo de um algoritmo que executa esse rapidamente é o algoritmo de busca clássico binário, para encontrar um elemento em uma lista já ordenada de elementos. 

Se você não sabe o que busca binária faz, Eu vou explicar isso para você muito rapidamente. Vamos dizer que você está olhando para o número 3 neste array de inteiros. Menciona-se o elemento do meio da matriz e pergunta: "É o elemento que eu quero superior, igual ou menos do que isso?" Se for igual, então ótimo. Você encontrou o elemento, e está feito. Se for maior, então você sabe o elemento tem de estar no lado direito da matriz, e você só pode olhar para que, no futuro, e se ele é menor, então você sabe que tem que estar no lado esquerdo. Este processo é então repetido com a matriz de menor tamanho até que o elemento correto seja encontrado. 

Este poderoso algoritmo corta o tamanho da matriz no meio com cada operação. Assim, para encontrar um elemento em uma matriz classificada de tamanho 8, no máximo (log ₂ 8), ou 3 dessas operações, verificar o elemento central, em seguida, a matriz de corte em meia será exigido, Considerando uma matriz de tamanho 16 leva (log ₂ 16), ou quatro operações. Isso é apenas uma operação mais para uma matriz dobrou de tamanho. A duplicação do tamanho da matriz aumenta o tempo de execução de apenas um pedaço deste código. Mais uma vez, o elemento de controlo do meio da lista, então a divisão. Assim, diz-se para operar em tempo logarítmica, O (log n). Mas espere, você diz, isto não depende de onde na lista o elemento que você está procurando é? E se o primeiro elemento você olhar passa a ser a pessoa certa? Então, ele só tem uma operação, não importa quão grande a lista é. 

Bem, isso é por que os cientistas de computador têm mais termos para a complexidade assintótica que refletem o melhor caso e pior desempenho de um algoritmo. Mais propriamente, os limites superior e inferior em tempo de execução. No melhor dos casos por busca binária, é nossa elemento ali no meio, e você obtê-lo em tempo constante, não importa quão grande o resto da matriz é. O símbolo utilizado para isso é Ω. Assim, este algoritmo é dito a correr em Ω (1). No melhor dos casos, ela encontra o elemento de forma rápida, não importa quão grande é a matriz, mas, no pior caso, que tem de desempenhar (log n) cheques divisão da matriz para encontrar o elemento certo. Limites pior superiores são referidos com o grande "O", que você já sabe. Então, é O (log n), mas Ω (1). 

Uma busca linear, pelo contrário, em que você anda através de cada elemento da matriz para encontrar o que você quer, é a melhor Ω (1). Mais uma vez, o primeiro elemento que você deseja. Então, não importa o quão grande é a matriz. No pior dos casos, é o último elemento na matriz. Então, você tem que passar por todos os n elementos na matriz para encontrá-lo, como se você estivesse olhando para um 3. Então, ele é executado em tempo O (n) pois é proporcional ao número de elementos na matriz. 

Mais um símbolo usado é Θ. Isso pode ser usado para descrever algoritmos onde os casos melhores e piores são os mesmos. Este é o caso dos algoritmos seqüência de comprimento que falamos anteriormente. Isto é, se armazená-lo em uma variável antes nós armazenamos a corda e acessá-lo mais tarde em tempo constante. Não importa que número estamos armazenando nessa variável, nós vamos ter que olhar para ele. O melhor caso é, olhamos para ele e encontrar o comprimento da corda. Assim Ω (1), ou melhor, caso o tempo constante. O pior caso é, olharmos para ele e encontrar o comprimento da corda. Assim, ó (1) ou constante de tempo no pior caso. Então, uma vez que o melhor caso e pior dos casos são os mesmos, isso pode ser dito para ser executado em tempo Θ (1). 

Em resumo, temos boas maneiras de raciocinar sobre a eficiência códigos sem saber nada sobre o tempo do mundo real que tomam para correr, que é afetado por muitos fatores externos, incluindo hardware diferentes, software, ou as especificidades do seu código. Além disso, ela nos permite raciocinar bem sobre o que vai acontecer quando o tamanho dos aumentos de entradas. 

Se você estiver executando em O (n) algoritmo ², ou pior, um O (2 ⁿ) algoritmo, um dos mais rápidos tipos de cultivo, você vai realmente começar a notar a desaceleração quando você começar a trabalhar com grandes quantidades de dados. 

Essa é a complexidade assintótica. Obrigado.