Très bien, alors, la complexité de calcul. Juste un peu d'un avertissement Avant de nous plonger dans de trop far-- ce sera probablement parmi les les choses les plus de maths-lourd nous parlons dans CS50. Espérons que ce ne sera pas trop écrasante et nous allons essayer de vous guider dans le processus, mais juste un peu d'un avertissement juste. Il ya un peu des mathématiques en cause ici. Très bien, alors, afin de faire utilisation de nos ressources informatiques dans le réel monde-- il est vraiment important de comprendre les algorithmes et comment ils traitent les données. Si nous avons une très algorithme efficace, nous peut minimiser la quantité de ressources nous disposons pour traiter avec elle. Si nous avons un algorithme qui va prendre beaucoup de travail pour traiter un très vaste ensemble de données, il est va exiger plus et plus de ressources, ce qui est de l'argent, de la RAM, tout ce genre de trucs. 

Donc, être capable d'analyser une algorithme utilisant cet ensemble d'outils, essentiellement, demande à la question-- comment fonctionne cette échelle de l'algorithme comme on jette de plus en plus de données à elle? Dans CS50, la quantité de données que nous sommes travailler avec est assez petite. Généralement, nos programmes vont afin de fonctionner dans un deuxième ou less-- probablement beaucoup moins surtout au début. 

Mais pensez à une société qui traite avec des centaines de millions de clients. Et ils ont besoin pour traiter que les données de client. Comme le nombre de clients qu'ils avoir devient de plus en plus grande, il va exiger de plus en plus de ressources. Combien d'autres ressources? Eh bien, cela dépend de la façon dont nous analysons l'algorithme, utilisant les outils de cette boîte à outils. Lorsque nous parlons de la complexité de un algorithm-- qui, parfois, vous aurez entendre qu'elle a appelé le temps la complexité ou de l'espace de la complexité mais nous allons juste appeler complexity-- nous sommes généralement parler le pire scénario. Compte tenu de la pire tas de les données que nous pourrions jeter à elle, comment cet algorithme va traiter ou de traiter avec ces données? Nous appelons généralement le pire des cas l'exécution d'un grand-O de l'algorithme. Donc un algorithme peut être dit courir dans O n ou O n carré. Et plus sur ce que ceux qui signifie dans une seconde. 

Parfois, cependant, nous ne nous soucions sur le meilleur scénario. Si les données sont tout ce que nous voulions que ce soit et il était absolument parfait et nous avons envoyé cette parfaite ensemble de données grâce à notre algorithme. Comment serait-il gérer dans cette situation? On se réfère parfois à ce que grand-Omega, donc en contraste avec Big-O, Nous avons de grands-Omega. Big-Omega pour le meilleur scénario. Big-O pour le pire des scénarios. Généralement, quand on parle de la complexité d'un algorithme, nous parlons de la le pire des cas. Alors garde cela en tête. 

Et dans cette classe, nous sommes généralement aller de quitter l'analyse rigoureuse de côté. Il ya sciences et des champs consacré à ce genre de choses. Lorsque nous parlons de raisonnement grâce à des algorithmes, que nous ferons morceau par morceau pour beaucoup algorithmes que nous parlons dans la classe. Nous sommes vraiment juste parler raisonnement avec le sens commun, pas avec des formules ou des preuves, ou quelque chose comme ça. Donc, ne vous inquiétez pas, nous ne serons pas se transformer en une grande classe de mathématiques. 

Donc je l'ai dit nous nous soucions de la complexité car il pose la question, comment nos algorithmes ne traitent plus grand et de plus grands ensembles de données étant jetés sur eux. Eh bien, ce qui est un ensemble de données? Qu'est-ce que je veux dire quand je dis cela? Cela signifie que tout ce que fait le plus sens dans le contexte, pour être honnête. Si nous avons un algorithme, la Processus Strings-- Nous sommes probablement parler de la taille de la chaîne. Voilà les données set-- la taille, le nombre des caractères qui composent la chaîne. Si nous parlons d'une algorithme qui traite les fichiers, nous pourrions parler de la façon dont de nombreux kilo-octets comprennent ce fichier. Et qui est le jeu de données. Si nous parlons d'un algorithme qui gère les tableaux, plus généralement, comme algorithmes de tri ou la recherche des algorithmes, nous parlons probablement sur le nombre des éléments qui composent un tableau. 

Maintenant, nous pouvons mesurer une algorithm-- en particulier, quand je dis que nous pouvons mesurer un algorithme, je dire que nous pouvons mesurer de nombreuses ressources qu'il prend. Si ces ressources sont, combien octets de RAM-- ou Mo de RAM il utilise. Ou combien de temps qu'il faut pour exécuter. Et nous pouvons appeler cela mesurer, arbitrairement, de f n. Où n est le nombre de éléments de l'ensemble de données. Et f de n est le nombre de quadragénaires. Combien d'unités de ressources ne il exige de traiter ces données. 

Maintenant, nous ne nous soucions pas fait sur ce que f de n est exactement. En fait, nous will-- très rarement Certainement jamais dans ce que je class-- plonger dans quelle vraiment profonde analyse de ce f de n est. Nous allons juste parler de ce que f n est d'environ ou qui tend à. Et la tendance d'un algorithme est dicté par son terme d'ordre le plus élevé. Et nous pouvons voir ce que je dire par là en prenant un oeil à un exemple plus concret. 

Alors disons que nous avons trois algorithmes différents. Le premier d'entre eux prend n cubes, certaines unités de ressources pour traiter un ensemble de données de taille n. Nous avons un deuxième algorithme qui prend n cubes ainsi que des ressources n carrés pour traiter un ensemble de données de taille n. Et nous avons un troisième algorithme qui exécute in-- que prend n moins cubes 8n carré plus 20 n unités de ressources pour traiter un algorithme avec l'ensemble de taille n données. 

Maintenant, encore une fois, nous allons vraiment pas pour entrer dans ce niveau de détail. Je suis vraiment ai juste ces up ici comme une illustration d'un point que je vais être prise dans une seconde, qui est que nous nous soucions seulement vraiment à propos de la tendance des choses que les ensembles de données deviennent plus grands. Donc, si l'ensemble de données est petite, il ya fait une très grande différence dans ces algorithmes. Le troisième algorithme y prend 13 fois plus longtemps, 13 fois la quantité de ressources à courir par rapport à la première. 

Si notre ensemble de données est la taille 10, qui est plus grand, mais pas nécessairement énorme, nous pouvons voir qu'il ya en fait un peu de différence. Le troisième algorithme devient plus efficace. Il est environ 40% en fait - ou 60% plus efficace. Il faut 40% du temps. Il peut run-- il peut prendre 400 unités de ressources pour traiter un ensemble de données de taille 10. Alors que le premier algorithme, par contraste, prend 1.000 unités de ressources pour traiter un ensemble de données de taille 10. Mais regardez ce qui se passe comme nos chiffres deviennent encore plus grand. 

Or, la différence entre ces algorithmes commencer à devenir un peu moins apparente. Et le fait qu'il y a ordre inférieur terms-- ou plutôt, termes avec exponents-- inférieure commencer à devenir hors de propos. Si un ensemble de données est de taille 1000 et le premier algorithme fonctionne dans un milliards étapes. Et le deuxième algorithme fonctionne en un milliard et un million étapes. Et le troisième algorithme exécute dans un peu moins d'un milliard d'étapes. Il est à peu près un milliard d'étapes. Ces termes d'ordre inférieur commencent pour devenir vraiment pertinent. Et juste pour vraiment marteler le point-- si l'entrée de données est une taille de million-- tous les trois de ces à peu près prendre une quintillion-- si mes calculs sont étapes correct-- pour traiter une entrée de données de la taille d'un million. Cela fait beaucoup d'étapes. Et le fait que l'un d'eux pourrait prendre une couple de 100.000, ou un couple 100 encore moins quand millions nous parlons d'un certain nombre que big-- il est un peu hors de propos. Ils ont tous tendance à prendre n cubes environ, et ainsi nous aurions effectivement reporter à l'ensemble de ces algorithmes comme étant de l'ordre de n cubes ou Big-O de n cubes. 

Voici une liste de quelques-uns des plus classes de complexité de calcul communes que nous allons rencontrer dans algorithmes, en général. Et aussi spécifiquement dans CS50. Ceux-ci sont commandés à partir généralement plus rapide au sommet, généralement le plus lent à en bas. Donc algorithmes de constante de temps ont tendance être le plus rapide, quel que soit de la taille de la entrée de données vous passez. Ils prennent toujours une opération ou une unité de ressources pour faire face à. Il pourrait être 2, il pourrait être trois, il peut être 4. Mais il est un nombre constant. Il ne varie pas. 

Les algorithmes de temps logarithmique sont un peu mieux. Et un très bon exemple de un algorithme logarithmique vous avez sûrement vu désormais est la déchirer du livre de téléphone à trouver Mike Smith dans le livre de téléphone. Nous avons réduit le problème de moitié. Et de manière plus large n obtient et plus grande et larger-- En fait, chaque fois que vous double n, il prend seulement un pas de plus. Voilà donc beaucoup mieux que, par exemple, le temps linéaire. Qui est si vous doublez n, il prend le double du nombre d'étapes. Si vous triplez n, il faut tripler le nombre d'étapes. Une étape par unité. 

Puis les choses deviennent un peu plus-- peu moins grande à partir de là. Vous avez le temps rythmique linéaire, parfois appelé journal temps linéaire ou tout simplement n log n. Et nous allons un exemple d'un algorithme qui points en n log n, ce qui est encore mieux time-- quadratique de n au carré. Ou polynomiale, deux n un nombre quelconque supérieur à deux. Ou le temps exponentielle, ce qui est encore worse-- C au n. Ainsi, certains nombre constant porté à la puissance de la taille de l'entrée. Donc, si il ya 1,000-- si le entrée de données est de taille 1000, il faudrait C à la puissance 1000 e. Il est bien pire que le temps polynomiale. 

Temps factorielle est encore pire. Et en fait, il ne sont pas vraiment Il existe des algorithmes de temps infini, tels que, soi-disant sort-- stupide dont travail consiste à mélanger de façon aléatoire un tableau puis vérifier si elle est triée. Et si elle est pas, au hasard mélangez à nouveau le tableau et vérifier pour voir si elle est triée. Et comme vous pouvez probablement imagine-- vous pouvez imaginer une situation où, dans le pire des cas, que la volonté jamais réellement commencer avec le tableau. Cet algorithme courrait toujours. Et ce serait une algorithme de temps infini. Espérons que vous ne serez pas écrivez tout moment factoriel ou infini algorithmes dans CS50. 

Donc, nous allons prendre un peu plus regard concret sur certains simple classes de complexité de calcul. Nous avons donc une example-- ou deux exemples ici-- des algorithmes de constante de temps, qui prennent toujours une seule opération dans le pire des cas. Donc la première example-- nous avons une fonction appelé 4 pour vous, qui prend un tableau de taille de 1000. Mais alors, semble-t- ne fait pas regarder au it-- ne se soucie pas vraiment ce qui est à l'intérieur, de ladite matrice. Toujours retourne juste quatre. Ainsi, cet algorithme, malgré le fait qu'il prend 1.000 éléments n'a pas faire quelque chose avec eux. Retourne juste quatre. Il est toujours une seule étape. 

En fait, ajouter 2 qui nums-- nous avons vu auparavant que well-- processus juste deux entiers. Il est pas une seule étape. Il est en fait un couple d'étapes. Vous obtenez un, vous obtenez b, vous les ajoutez ensemble, et sortie des résultats. Donc, il est 84 étapes. Mais il est toujours constante, indépendamment de a ou b. Vous devez obtenir un, obtenez b, ajouter ensemble, sortie du résultat. Voilà donc un algorithme de temps constant. 

Voici un exemple d'un linéaire algorithm-- de temps un algorithme qui gets-- qui prend une étape supplémentaire, le cas échéant, que votre entrée augmente de 1. Donc, disons que nous recherchons le nombre 5 à l'intérieur d'un tableau. Vous pourriez avoir une situation où vous pouvez le trouver assez tôt. Mais vous pourriez aussi avoir une situation où il pourrait être le dernier élément du tableau. Dans un tableau de taille 5, si nous recherchons pour le numéro 5. Il faudrait 5 étapes. Et en fait, imaginez qu'il ya pas 5 partout dans ce tableau. En fait, nous avons encore à regarder chaque élément du tableau afin de déterminer si oui ou non il est 5. 

Donc, dans le pire des cas, ce qui est ce que l'élément est la dernière dans le tableau ou ne existe pas du tout. Nous avons encore à regarder tous les n éléments. Et si cet algorithme fonctionne en temps linéaire. Vous pouvez confirmer que par extrapolant un peu en disant, si nous avions un tableau 6-élément et nous étions à la recherche pour le numéro 5, il pourrait prendre 6 étapes. Si nous avons un ensemble de 7 éléments et nous recherchons pour le numéro 5. Il pourrait prendre 7 étapes. Comme nous ajoutons un élément de plus à notre tableau, il prend un pas de plus. Voilà un algorithme linéaire dans le pire des cas. 

Couple de questions pour vous. Quelle est la runtime-- ce qui est le pire des cas d'exécution de ce bout de code particulier? Je dois donc une boucle de 4 ici qui fonctionne De J est égal à 0, tout le chemin jusqu'à m. Et ce que je vois ici, est que le corps de la boucle fonctionne en temps constant. Donc, en utilisant la terminologie nous avons déjà parlé ce about-- serait le pire des cas exécution de cet algorithme? Prenez une seconde. La partie interne de la boucle fonctionne en temps constant. Et la partie extérieure de la boucle va courir m fois. Alors, quel est le pire des cas runtime ici? Avez-vous deviné Big-O de m? Vous avez raison. 

Que diriez-vous les uns les autres? Cette fois, nous avons une boucle à l'intérieur d'une boucle. Nous avons une boucle externe qui va de zéro à p. Et nous avons une boucle interne qui fonctionne de zéro à p, et à l'intérieur de cela, Je déclare que le corps de la boucle fonctionne en temps constant. Alors, quel est le pire des cas d'exécution de ce bout de code particulier? Eh bien, encore une fois, nous avons une boucle externe qui exécute p fois. Et chaque itération time-- de cette boucle, plutôt. Nous avons une boucle intérieure qui fonctionne aussi p fois. Et puis à l'intérieur de cela, il ya la constante petit extrait time-- il. 

Donc, si nous avons une boucle externe qui exécute p fois intérieur de ce qui est une boucle intérieure qui p exécute ce qui est times-- le pire des cas d'exécution de ce bout de code? Avez-vous deviné Big-O de p carré? 

Je suis Doug Lloyd. Ceci est CS50.