>> Muy bien, así, la complejidad computacional.
Sólo un poco de una advertencia Antes de profundizar en demasiados far--
esto probablemente va a ser entre las cosas más pesado de matemáticas
hablamos en CS50.
Esperemos que no sea demasiado abrumador y vamos a tratar de guiar
a través del proceso, pero sólo un poco de una advertencia justa.
Hay un poco de matemáticas involucradas aquí.
De acuerdo, con el fin de hacer uso de nuestros recursos computacionales
en lo real mundo-- es realmente importante entender algoritmos
y cómo se procesan los datos.
Si tenemos una realidad algoritmo eficiente, nos
puede reducir al mínimo la cantidad de recursos que tenemos disponible para tratar con él.
Si tenemos un algoritmo que se va a tomar un montón de trabajo
para procesar una realidad gran conjunto de datos, es
va a requerir más y más recursos, que
es el dinero, la memoria RAM, todo ese tipo de cosas.
>> Por lo tanto, ser capaz de analizar una algoritmo que utiliza este conjunto de herramientas,
básicamente, se pregunta el pregunta-- ¿cómo funciona esta escala algoritmo
como tiramos más y más datos en él?
En CS50, la cantidad de datos que estamos trabajar con es bastante pequeña.
En general, nuestros programas van para ejecutarse en un segundo o less--
probablemente mucho menos sobre todo desde el principio.
>> Pero piensa en una empresa que ofertas con cientos de millones de clientes.
Y necesitan para procesar que los datos del cliente.
A medida que el número de clientes a los que tienen hace más grande y más grande,
que va a requerir más y más recursos.
¿Cuántos más recursos?
Bueno, eso depende de cómo analizamos el algoritmo,
utilizando las herramientas de esta caja de herramientas.
Cuando hablamos de la complejidad de un algorithm-- que a veces tendrás
escuchar su pronunciación conoce como tiempo complejidad o espacio complejidad
pero sólo vamos llamar complexity--
estamos hablando en general, el peor de los casos.
Teniendo en cuenta el peor pila absoluta de datos que podríamos estar lanzando en él,
cómo se va a este algoritmo procesar o tratar con esos datos?
Por lo general, llamamos el peor de los casos tiempo de ejecución de un algoritmo grande-O.
Así que un algoritmo podría decirse que ejecutar en O de n u O de n al cuadrado.
Y más de lo aquellos quiere decir en un segundo.
>> A veces, sin embargo, nos importa sobre el mejor de los casos.
Si los datos son todo lo que queríamos que sea y que era absolutamente perfecto
y estábamos enviando esta perfecta un conjunto de datos a través de nuestro algoritmo.
¿Cómo sería manejar en esa situación?
A veces nos referimos a que a medida big-Omega, por lo que en contraste con la gran-O,
tenemos grandes Omega.
Big-Omega para el mejor de los casos.
Big-O para el peor de los casos.
Generalmente, cuando se habla de la complejidad de un algoritmo,
estamos hablando de la en el peor escenario.
Así que tenlo en mente.
>> Y en esta clase, estamos generalmente va para dejar el análisis riguroso de lado.
Hay ciencias y campos dedicado a este tipo de cosas.
Cuando hablamos de razonamiento a través de algoritmos,
que haremos pieza por pieza para muchos algoritmos que nos hablan de la clase.
Realmente estamos hablando sólo de razonamiento a través de él con el sentido común,
no con fórmulas, o pruebas, ni nada de eso.
Así que no se preocupe, nosotros no vamos a ser convirtiéndose en una clase de matemáticas grande.
>> Así que le dije que nos preocupamos por la complejidad porque hace la pregunta, ¿cómo
no manejan nuestros algoritmos más grande y grandes conjuntos de datos que son lanzados contra ellos.
Bueno, lo que es un conjunto de datos?
¿Qué quise decir cuando dije eso?
Significa lo aprovecha al máximo sentido en el contexto, para ser honesto.
Si tenemos un algoritmo, el Procesos Strings-- estamos probablemente
hablando sobre el tamaño de la cadena.
Eso es los datos definido-- el tamaño, el número
de caracteres que componen la cadena.
Si estamos hablando de un algoritmo que procesa los archivos,
podríamos estar hablando de cómo muchos kilobytes comprenden ese archivo.
Y ese es el conjunto de datos.
Si estamos hablando de un algoritmo que maneja arrays de manera más general,
tales como algoritmos de ordenación o la búsqueda de algoritmos,
probablemente estamos hablando de la serie de los elementos que conforman una matriz.
>> Ahora, podemos medir una algorithm-- en particular,
cuando digo que podemos mido un algoritmo, que
significa que podemos medir la muchos recursos que ocupa.
Ya sea que esos recursos son, cuántos bytes de RAM-- o megabytes de RAM
usa.
¿O cuánto tiempo se tarda en ejecutar.
Y podemos llamar a esto medir, de manera arbitraria, f de n.
Donde n es el número de elementos en el conjunto de datos.
Y f de n es el número de tantos.
¿Cuántas unidades de recursos hace se requiere para procesar esos datos.
>> Ahora, en realidad no nos importa acerca de lo que f de n es exactamente.
De hecho, muy raramente Voluntad-- sin duda nunca se en este class-- I
bucear en cualquier realmente profundo análisis de lo que f de n es.
Sólo vamos a hablar de lo f de n es de aproximadamente o lo que tiende a.
Y la tendencia de un algoritmo es dictado por su término más alto orden.
Y podemos ver lo que decir con que al tomar
Una mirada a un ejemplo más concreto.
>> Así que vamos a decir que tenemos tres algoritmos diferentes.
El primero de los cuales tiene n cubos, algunas unidades de recursos
para procesar un conjunto de datos de tamaño n.
Tenemos un segundo algoritmo que toma n cubos más recursos n al cuadrado
para procesar un conjunto de datos de tamaño n.
Y tenemos una tercera algoritmo que se ejecuta en-- que
ocupa n 8n menos al cubo cuadrado más 20 n unidades de recursos
para procesar un algoritmo con conjunto de tamaño n de datos.
>> Ahora, de nuevo, que realmente no vamos para entrar en este nivel de detalle.
Estoy realmente sólo tengo estas arriba aquí como una ilustración de un punto
que yo voy a ser decisiones en un segundo, lo que
es que sólo nos importa acerca de la tendencia de las cosas
como los conjuntos de datos se hacen más grandes.
Así que si el conjunto de datos es pequeño, hay en realidad una diferencia bastante grande
en estos algoritmos.
El tercer algoritmo allí toma 13 veces más,
13 veces la cantidad de recursos para funcionar en relación con la primera.
>> Si nuestro conjunto de datos es de tamaño 10, que es más grande, pero no necesariamente enorme,
podemos ver que hay en realidad un poco de diferencia.
El tercer algoritmo se vuelve más eficiente.
Se trata en realidad del 40% - o 60% más eficiente.
Se tarda 40% la cantidad de tiempo.
Puede run-- puede tomar 400 unidades de recursos
para procesar un conjunto de datos de tamaño 10.
Mientras que la primera algoritmo, por el contrario,
tiene 1.000 unidades de recursos para procesar un conjunto de datos de tamaño 10.
Pero mira lo que pasa como nuestros números se ponen aún más grande.
>> Ahora, la diferencia entre estos algoritmos
empezar a ser un poco menos aparente.
Y el hecho de que hay de orden inferior terms-- o más bien,
términos con menor exponents-- empezar a ser irrelevante.
Si un conjunto de datos es de tamaño 1000 y el primer algoritmo
corre en unos mil millones de pasos.
Y el segundo algoritmo se ejecuta en mil millones y un millón de pasos.
Y la tercera algoritmo se ejecuta en poco menos de mil millones de pasos.
Es más o menos mil millones de pasos.
Esos términos de orden inferior comienzan para llegar a ser realmente irrelevante.
Y sólo para realmente martillo casa el point--
si la entrada de datos es de tamaño a millones-- estos tres o menos
tomar uno quintillion-- si mis matemáticas es pasos correct--
para procesar una entrada de datos del tamaño de un millón.
Eso es un montón de pasos.
Y el hecho de que uno de ellos podría tomar un par de 100.000, o una pareja 100
millones menos aún cuando estamos hablando de un número
que big-- es algo irrelevante.
Todos ellos tienden a tomar aproximadamente n en cubos,
y así podríamos realmente referirse a todos estos algoritmos
como estando en el orden de n en cubos o grande-O de n cubos.
>> Aquí está una lista de algunos de los más clases comunes complejidad computacional
que vamos encontramos en algoritmos, por lo general.
Y también específicamente en CS50.
Estos están ordenados de generalmente más rápida en la parte superior,
a generalmente más lento en la parte inferior.
Así algoritmos de tiempo constante tienden ser el más rápido, sin tener en cuenta
del tamaño de la entrada de datos se pasa en.
Ellos siempre tienen una sola operación o una unidad de recursos para hacer frente a.
Podría ser 2, podría ser de 3, podría ser 4.
Pero es un número constante.
No varía.
>> Algoritmos tiempo logarítmicas son ligeramente mejor.
Y un buen ejemplo de un algoritmo de tiempo logarítmica
seguramente has visto por ahora es el desgarrando de la guía telefónica
encontrar Mike Smith en la guía telefónica.
Cortamos el problema a la mitad.
Y así, a medida que n se hace más grande y más grande y larger--
de hecho, cada vez que el doble n, sólo se necesita un paso más.
Así que eso es mucho mejor que, por ejemplo, el tiempo lineal.
¿Qué es si se duplica n, que toma el doble del número de pasos.
Si Triple N, se necesita triplicar el número de pasos.
Un paso por unidad.
>> Luego las cosas se ponen un poco más-- poco menos grande de allí.
Tienes tiempo rítmico lineal, a veces llamado registro de tiempo lineal o simplemente n log n.
Y vamos a un ejemplo de un algoritmo que
carreras en n log n, lo que es aún mejor que cuadrática tiempo-- n al cuadrado.
O el tiempo polinomio, n de dos cualquier número mayor que dos.
O tiempo exponencial, lo que es aún worse-- C para el n.
Así que algunos número constante elevó hasta el poder del tamaño de la entrada.
Así que si hay 1,000-- si el la entrada de datos es de tamaño 1000,
tomaría C al poder 1000a.
Es mucho peor que tiempo polinomial.
>> Tiempo factorial es aún peor.
Y de hecho, en realidad lo hacen Existen algoritmos de tiempo infinito,
tales como, los llamados sort-- estúpida cuya trabajo consiste en mezclar aleatoriamente un conjunto
y luego compruebe ya sea ordenadas.
Y si no es así, al azar mezclar la matriz de nuevo
y comprobar para ver si se trata de resolver el problema.
Y como usted probablemente puede imagine-- se puede imaginar una situación
donde en el peor de los casos, que la voluntad En realidad nunca comenzar con la matriz.
Ese algoritmo iría para siempre.
Y por lo que sería un algoritmo de tiempo infinito.
Esperemos que no va a escribir cualquier momento factorial o infinito
algoritmos en CS50.
>> Por lo tanto, vamos a echar un poco más aspecto concreto en algún simple
clases de complejidad computacional.
Así que tenemos un ejemplo-- o dos ejemplos aquí--
de algoritmos de tiempo constantes, que siempre tomar
una sola operación en el peor de los casos.
Así que la primera ejemplo-- tenemos una función
llamada 4 para usted, que toma una matriz de tamaño 1000.
Pero entonces, aparentemente en realidad no mirar
en it-- no le importa realmente lo que es dentro de ella, de esa matriz.
Siempre simplemente devuelve cuatro.
Por lo tanto, ese algoritmo, a pesar del hecho de que
tiene 1.000 elementos no hacer nada con ellos.
Sólo devuelve cuatro.
Es siempre un solo paso.
>> De hecho, añadir 2 nums-- que que hemos visto antes como bien--
simplemente procesa dos enteros.
No es un solo paso.
En realidad es un par de pasos.
Usted recibe una, se obtiene b, se agregan juntos, y ustedes, los resultados de salida.
Así que es 84 pasos.
Pero siempre es constante, independientemente de a o b.
Tienes que conseguir una, obtener b, agregue juntos, el resultado de salida.
Así que eso es un algoritmo de tiempo constante.
>> He aquí un ejemplo de un algorithm-- tiempo lineal
un algoritmo que gets-- que toma un paso adicional, posiblemente,
como su entrada crece un 1.
Así que, digamos que estamos buscando el número 5 en el interior de una matriz.
Es posible que tenga una situación en la usted lo puede encontrar bastante temprano.
Pero también podría tener una situación donde
podría ser el último elemento de la matriz.
En una matriz de tamaño 5, si estamos buscando el número 5.
Tomaría 5 pasos.
Y de hecho, imagino que hay No 5 en cualquier parte de esta matriz.
Todavía en realidad tenemos que mirar cada elemento de la matriz
Para determinar si 5 es allí.
>> Así que en el peor de los casos, y es que el elemento es la última en la matriz
o no existe en absoluto.
Todavía tenemos que mirar todos los n elementos.
Y así, este algoritmo se ejecuta en tiempo lineal.
Puede confirmar que por extrapolar un poco al decir:
si tuviéramos una matriz de 6 elementos y que estábamos buscando para el número 5,
puede ser que tome 6 pasos.
Si tenemos un conjunto de 7 elementos y estamos buscando el número 5.
Puede ser que tome 7 pasos.
A medida que agregamos un elemento más a nuestro matriz, que se necesita un paso más.
Eso es un algoritmo lineal En el peor de los casos.
>> Pareja preguntas rápidas para usted.
¿Cuál es la runtime-- lo que es el peor de los casos-runtime
de este fragmento de código en particular?
Así que tengo un bucle de 4 aquí que corre desde j es igual a 0, todo el camino hasta m.
Y lo que estoy viendo aquí, es que el cuerpo del bucle se ejecuta en tiempo constante.
Así, utilizando la terminología que ya hemos hablado sobre-- lo
sería el peor de los casos tiempo de ejecución de este algoritmo?
Tome un segundo.
La parte interna del bucle corre en tiempo constante.
Y la parte exterior de la bucle se va a ejecutar m veces.
¿Cuál es el peor de los casos el tiempo de ejecución en esta lista?
¿Sabía usted adivina grande-O de m?
Usted tendría razón.
>> ¿Qué hay de otra?
Esta vez tenemos una bucle dentro de un bucle.
Tenemos un bucle exterior que va desde cero a p.
Y tenemos un bucle interno que se ejecuta de cero a p, y en el interior de eso,
Declaro que el cuerpo de la bucle se ejecuta en tiempo constante.
¿Cuál es el peor de los casos el tiempo de ejecución de este fragmento de código en particular?
Bueno, de nuevo, tenemos una lazo externo que se ejecuta p veces.
Y cada iteración tiempo-- de ese bucle, más bien.
Tenemos un bucle interno que también corre p veces.
Y luego dentro de eso, está el constante pequeño fragmento tiempo-- allí.
>> Así que si tenemos un bucle exterior que corre p veces dentro de los cuales es
un bucle interior que corre p veces-- lo que es
el peor de los casos-runtime de este fragmento de código?
¿Sabía usted adivina grande-O de p al cuadrado?
>> Soy Doug Lloyd.
Esto es CS50.