[Powered by Google Translate] Vostede probablemente xa escoitou persoas falaren sobre un algoritmo rápido e eficiente para a execución da súa tarefa particular, pero o que exactamente significa isto para un algoritmo para ser rápido ou eficaz? Ben, non está falando dunha medición en tempo real, como segundos ou minutos. Isto é porque o hardware do ordenador e programa pode variar drasticamente. O meu programa pode ser máis lento que o seu, porque eu estou correndo nun ordenador antigo, ou porque eu ocorrer de estar xogando un xogo online ao mesmo tempo, que toda a memoria hogging meu, ou eu podería estar rodando o meu programa a través dun programa diferente que comunica co aparello de forma diferente a un nivel baixo. É como comparar mazás e laranxas. Só porque o meu ordenador máis lento leva máis que a súa para dar de volta unha resposta non significa que ten o máis eficiente. 

Entón, xa que non podemos comparar directamente os tempos de execución de programas en segundos ou minutos, como podemos comparar dous algoritmos diferentes independentemente do seu hardware ou ambiente de software? Para crear unha forma máis uniforme de medición da eficiencia algorítmica, científicos da computación e matemáticas desenvolveron conceptos para a medición da complexidade asintótica dun programa e unha notación chamada 'Ohnotation Big' para describir este. A definición formal é que unha función f (x) roda na fin de g (x) se existe un certo valor (x), x e ₀ unha constante, C, para o cal f (x) é menor que ou igual a que constante veces g (x) para todo x maior que x ₀. 

Pero non se asombran coa definición formal. O que isto realmente significa en termos menos teóricas? Ben, é basicamente unha forma de analizar quão rápido tempo de execución dun programa crece assintoticamente. Ou sexa, como o tamaño dos seus insumos aumenta cara ao infinito, digamos, está unha matriz de clasificación de tamaño 1000 en comparación con unha matriz de tamaño 10. Como o tempo de execución do seu programa de crecer? Por exemplo, imaxine conta do número de caracteres nunha corda a maneira máis sinxela  camiñando por toda a cadea letra por letra e engadindo un a un contador para cada personaxe. Este algoritmo está dito para ser executado en tempo lineal no que se refire ao número de caracteres, 'N' na cadea. En suma, é executado en O (n). Por que isto? Así, utilizar esta visión, o tempo necesario para atravesar toda a cadea é proporcional ao número de caracteres. Contando o número de caracteres nunha secuencia de 20 caracteres vai ter o dobre do tempo que sexa preciso para contar os caracteres nunha secuencia de 10 caracteres porque ten que mirar para todos os personaxes e cada personaxe ten a mesma cantidade de tempo para ollar. A medida que aumenta o número de caracteres, o tempo de execución pode aumentar linearmente co tempo de entrada. 

Agora, imagine se decide que o tempo lineal, O (n), pero non foi rápido abondo para ti? Quizais está almacenando grandes secuencias, e non pode pagar o tempo extra que sería necesario para percorrer todos os seus carácteres de conta un-por-un. Entón, decide probar algo diferente. E se ocorrer para xa almacenar o número de caracteres na secuencia, digamos, nunha variable chamada 'len' no inicio do programa, antes almacenado o primeiro personaxe na súa corda? Entón, todo o que tes que facer agora para descubrir a lonxitude da corda, é comprobar que o valor da variable. Non ten que ollar para a propia cadea, en todo, e acceder ao valor dunha variable como len é considerado unha operación de tempo constante assintoticamente, ou O (1). Por que isto? Ben, lembre que a complexidade asintótica significa. O que cambia o tempo de execución como o tamaño dos seus insumos medra? 

Diga que estaba tentando obter o número de caracteres nunha secuencia grande. Ben, non importa o quão grande facer a secuencia, ata un millón de caracteres, todo o que tes que facer para atopar a lonxitude da corda con esta visión, é a lectura do valor da variable de len, que xa fixo. A lonxitude de entrada, é dicir, a lonxitude da corda que está intentando atopar, non afecta a todos o quão rápido o programa é executado. Esta parte do seu programa sería executado igualmente rápido en unha cadea de caracteres e unha secuencia de mil caracteres, e é por iso que este programa sería referido como sendo executado en tempo constante con respecto ao tamaño de entrada. 

Por suposto, hai unha desvantaxe. Gasta espazo de memoria adicional no seu ordenador almacenar a variable e todo o tempo extra que leva para facer o almacenamento real da variable, pero o punto aínda está de pé, descubrir canto tempo a súa secuencia foi non depende da lonxitude da corda en todo. Entón, é executado en O (1) ou de tempo constante. Isto certamente non ha de significar que o código é executado en unha etapa, pero non importa cantos pasos se, se non se modifica o tamaño das entradas, aínda é assintoticamente constante que representamos con O (1). 

Como probablemente pode adiviñar, Existen varios grandes runtimes O para medir con algoritmos. O (n) ² algoritmos son assintoticamente máis lento que o (n) algoritmos. Isto é, como o número de elementos (n) aumenta, Finalmente, o (n) ² algoritmos vai levar máis tempo que o (n) para realizar algoritmos. Iso non significa que o (n) algoritmos sempre executar máis rápido que o (n) ² algoritmos, mesmo no mesmo ambiente, o mesmo hardware. Quizais para pequenos tamaños de entrada,  O (n) ² algoritmo pode realmente traballar máis rápido, pero, finalmente, como o tamaño de entrada aumenta para o infinito, a O (n) tempo de execución ² algoritmo acabará por eclipsar o tempo de execución do algoritmo O (n). Así como calquera función cuadrática matemáticas  eventualmente superar calquera función lineal, non importa o que unha cabeza de iniciar a función lineal comeza con. Se está a traballar con grandes cantidades de datos, algoritmos que son executados en O (n) ² realmente pode acabar retardando o seu programa, pero para tamaños de entrada pequenas, probablemente non vai nin entender. 

Outra complexidade asintótica é, tempo logarítmica, O (log n). Un exemplo dun algoritmo que executa este rápido é o algoritmo de procura clásico binario, para atopar un elemento nunha lista xa ordenada de elementos. 

Se non sabe o que busca binaria fai, Vou explicar isto para vostede moi rapidamente. Imos dicir que está mirando para o número 3 neste array de enteiros. Menciónase o elemento do medio da matriz e pregunta: "É o elemento que quero superior, igual ou menos que iso?" Se é igual, entón gran. Vostede atopou o elemento, e está feito. Se é maior, entón vostede sabe o elemento ten que estar no lado dereito da matriz, e só se pode ver que, no futuro, e se é menor, entón vostede sabe que ten que estar no lado esquerdo. Este proceso é entón repetida coa matriz de menor tamaño ata que o elemento correcto sexa atopado. 

Este poderoso algoritmo corta o tamaño da matriz no medio con cada operación. Así, para atopar un elemento nunha matriz clasificada de tamaño 8, como máximo (log ₂ 8), ou 3 destas operacións, comprobar o elemento central, a continuación, a matriz de corte en media será esixido, Considerando unha matriz de tamaño 16 leva (log ₂ 16), ou catro operacións. Isto é só unha operación máis para unha matriz dobrou de tamaño. A duplicación do tamaño da matriz aumenta o tempo de execución de só un anaco deste código. Unha vez máis, o elemento de control do medio da lista, entón a división. Así, di-se para operar en tempo logarítmica, O (log n). Pero espera, di, isto non depende de onde na lista o elemento que está a procurar é? E o primeiro elemento ollar pasa a ser a persoa ben? Entón, el só ten unha operación, non importa o grande a lista. 

Ben, é por iso que os científicos da computación teñen prazos máis a complexidade asintótica que reflicten o mellor caso e peor desempeño dun algoritmo. Máis propiamente, os límites superior e inferior en tempo de execución. No mellor dos casos por busca binaria, é a nosa elemento alí no medio, e obtelo en tempo constante, non importa quão grande o resto da matriz é. O símbolo utilizado para iso é Ω. Así, este algoritmo está dito a correr en Ω (1). No mellor dos casos, ela atopa o elemento de xeito rápido, non importa quão grande é a matriz, mais, no peor caso, que ten que desempeñar (log n) verifícase división da matriz para atopar o elemento certo. Límites peor superiores son referidos co gran "O", que xa sabes. Entón, é o (log n), pero Ω (1). 

Unha busca lineal, pola contra, en que anda a través de cada elemento da matriz para atopar o que quere, é a mellor Ω (1). Unha vez máis, o primeiro elemento que quere. Entón, non importa o quão grande é a matriz. No peor dos casos, é o último elemento na matriz. Entón, ten que pasar por todos os n elementos na matriz para atopalo, como se está mirando para un 3. Entón, é executado en tempo O (n) porque é proporcional ao número de elementos na matriz. 

Un símbolo usado é Θ. Isto pode ser usado para describir algoritmos onde os casos mellores e peores son os mesmos. Este é o caso dos algoritmos secuencia de lonxitude que falamos anteriormente. É dicir, se almacena-lo nunha variable antes nós gardados a corda e acceder a ela máis tarde en tempo constante. Non importa que número estamos almacenando nesa variable, nós imos ter que mirar para el. O mellor caso é, miramos para el e atopar a lonxitude da corda. Así Ω (1), ou mellor, se o tempo constante. O peor caso é, miramos para el e atopar a lonxitude da corda. Así, o (1) ou constante de tempo no peor caso. Entón, unha vez que o mellor caso e peor dos casos son os mesmos, iso pode ser dito para ser executado en tempo Θ (1). 

En resumo, temos boas maneiras de razoar sobre a eficiencia códigos sen saber nada sobre o tempo do mundo real que toman para correr, que é afectado por moitos factores externos, incluíndo hardware diferentes, software, ou as particularidades do seu código. Ademais, ela nos permite razoar ben sobre o que vai ocorrer cando o tamaño dos incrementos de entradas. 

Se está executando en O (n) algoritmo ², ou peor, un O (2 ⁿ) algoritmo, un dos máis rápidos tipo de cultivo, vai realmente comezar a notar a desaceleración cando comezar a traballar con grandes cantidades de datos. 

Esa é a complexidade asintótica. Grazas.