Computational ComplexityYouTube↗  IA↗(long shot)
Education  41.4K views 245 likes 12 dislikes   07 Oct 2015
CS50 2.4M subscribers United States YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
>> Добре, така, изчислителна сложност.
>> Na gut, so, Berechnungskomplexität.
Само малко на предупреждение преди да се потопите в твърде far--
Nur ein bisschen eine Warnung Bevor wir uns in zu far--
Това най-вероятно ще бъде сред най-тежки неща математика
Diese werden wahrscheinlich unter sein Die Mathematik-schwere Dinge
говорим за в CS50.
wir über in CS50 sprechen.
Надяваме се, че няма да бъде твърде преобладаващото и ние ще се опитаме да ви води
Hoffentlich wird es nicht zu überwältigend sein und wir werden versuchen, und führen Sie
чрез процеса, но малко на справедлив предупреждение.
durch den Prozess, aber nur ein bisschen eine faire Warnung.
Там е малко по- на математиката, участващи тук.
Es ist ein bisschen Mathe hier beteiligt.
Добре, така че, за да се направи използване на нашите изчислителни ресурси
Na gut, so, damit Verwendung unserer Rechenressourcen
в реалния world-- това е наистина важно да се разбере алгоритми
in der realen world-- es wirklich wichtig, um Algorithmen zu verstehen
и как те да обработва данни.
und wie sie Prozessdaten.
Ако имаме наистина ефикасен алгоритъм, ние
Wenn wir eine wirklich effizienten Algorithmus, wir
може да се намали количеството на ресурсите които са на разположение, за да се справят с него.
kann die Menge an Ressourcen zu minimieren wir zur Verfügung haben, damit umzugehen.
Ако имаме алгоритъм, който ще отнеме много работа
Wenn wir einen Algorithmus, wird eine Menge Arbeit
да обработи един наистина голям набор от данни, това е
um wirklich zu verarbeiten ein große Menge von Daten, ist es
ще изисква по- и повече ресурси, които
gehen, um mehr erforderlich und mehr Ressourcen, die
е пари, RAM, всички такива неща.
ist Geld, RAM, all solche Sachen.
>> Така че, е в състояние да анализира един алгоритъм използването на този инструмент набор,
>> Also, in der Lage, eine Analyse Algorithmus mit diesem Werkzeug-Set,
основно, моли question-- как този алгоритъм мащаб
Grundsätzlich fordert die question-- wie funktioniert dieser Algorithmus Skala
тъй като ние се хвърлят все повече и повече данни в него?
wie wir mehr und mehr Daten um sich werfen?
В CS50, количеството данни, ние сме работа с е доста малка.
In CS50, die Menge der Daten sind wir Arbeiten mit ist ziemlich klein.
Като цяло, нашите програми вървят да тичам в секунда или less--
Im Allgemeinen werden unsere Programme gehen um in einer zweiten oder less-- laufen
вероятно много по-малко особено в началото на деня.
wahrscheinlich viel weniger besonders früh.
>> Но мисля, че за една компания, която се занимава със стотици милиони потребители.
>> Aber zu einer Firma, die Angebote zu denken Hunderte von Millionen von Kunden.
И те трябва да се обработи този клиент данни.
Und sie brauchen, um zu verarbeiten dass Kundendaten.
Тъй като броят на клиентите им Трябва стане по-голям и по-голям,
Als die Anzahl der Kunden, die sie haben wird größer und größer,
това ще изисква все повече и повече ресурси.
es wird erforderlich mehr und mehr Ressourcen.
Колко повече ресурси?
Wie viele Ressourcen?
Е, това зависи от това как ние анализираме алгоритъм,
Nun, das hängt davon ab, wie analysieren wir den Algorithmus,
използване на инструментите в този инструментариум.
mit Hilfe der Tools in dieser Toolbox.
Когато говорим за сложността на един algorithm-- които Понякога ще
Wenn wir von der Komplexität der zu sprechen ein algorithm-- was manchmal werden Sie
чуете, че по-нататък време сложност или комплексност пространство
hören es an der Zeit bezeichnet Komplexität und Speicherkomplexität
но ние просто ще да се обадя complexity--
aber wir sind gerade dabei zu rufen complexity--
ние обикновено говорим за на най-лошия сценарий.
wir sind in der Regel reden das Worst-Case-Szenario.
Като се има предвид абсолютната лошия купчината данни, че бихме могли да се хвърлят в него,
Angesichts der absolute worst Haufen Daten, die wir auf sie zu werfen,
как е този алгоритъм ще обработват или се справят с тези данни?
wie wird dieser Algorithmus würde verarbeiten oder sich mit diesen Daten?
Ние обикновено наричаме най-лошия случай по време на работа на алгоритъм голям O.
Wir das Worst-Case-rufen in der Regel Laufzeit eines Algorithmus big-O.
Така че един алгоритъм може да се каже, тичам в O от п или O на п квадрат.
So könnte ein Algorithmus zu sagen laufen in O n oder O n quadriert.
И повече за това, тези, означава в секунда.
Und mehr über das, was diejenigen bedeuten, in einem zweiten.
>> Понякога, обаче, ние правим грижи за в най-добрия случай.
>> Manchmal aber geht uns über das Best-Case-Szenario.
Ако данните са всичко, което искахме тя да бъде и това беше абсолютно перфектно
Wenn die Daten alles, was wir wollten es zu sein und es war absolut perfekt
и ние бяхме изпращане на тази перфектна набор от данни чрез нашия алгоритъм.
und wir senden diesen perfekten Set von Daten über unser Algorithmus.
Как ще се справи в тази ситуация?
Wie wäre es in dieser Situation umgehen?
Ние понякога се позовават на нея като голям Omega, така че за разлика от големите O,
Wir beziehen uns manchmal, dass als Big-Omega, so im Gegensatz zu Big-O,
ние имаме голям Omega.
Wir haben big-Omega.
Big-Omega за в най-добрия случай.
Big-Omega für den besten Fall.
Big-O за най-лошия случай.
Big-O für den Fall der Fälle.
Обикновено, когато говорим за сложността на алгоритъм,
Im Allgemeinen, wenn wir sprechen Die Komplexität eines Algorithmus,
ние не говорим за най-лошия случай.
wir über das reden Worst-Case-Szenario.
Така че имайте това предвид.
So sollte man das im Hinterkopf.
>> И в този клас, което обикновено се случва, ние да напусне взискателен анализ настрана.
>> Und in dieser Klasse, wir sind in der Regel gehen um die strengen Analyse beiseite zu lassen.
Има науки и области посветен на този вид неща.
Es gibt Wissenschaften und Felder um diese Art von Sachen gewidmet.
Когато говорим за разсъждения чрез алгоритми,
Wenn wir über die Gründe sprechen durch Algorithmen,
което ние ще направим парче по парче за мнозина алгоритми говорим за в класа.
was wir Stück für Stück für viele zu tun Algorithmen, wir sprechen in der Klasse.
Ние сме наистина само се говори за размишлявате през него със здравия разум,
Wir sind wirklich nur darüber zu reden Argumentation durch sie mit gesundem Menschenverstand,
не с формули или доказателства, или нещо подобно.
nicht mit Formeln, oder Beweise, oder so etwas.
Така че не се притеснявайте, ние няма да се превръща в голям клас по математика.
Also keine Sorge, wir werden nicht sich in einen großen Math-Klasse.
>> Така че аз казах ние се грижим за сложност защото той задава въпроса, как
>> Also sagte ich: wir über die Komplexität Pflege weil sie die Frage, wie verlangt
да ни алгоритми справят по-големи и по-големи масиви от данни се хвърлят към тях.
haben unsere Algorithmen umgehen größer und wobei größere Datenmengen auf sie geworfen.
Е, какво е набор данни?
Nun, was ist ein Datensatz?
Какво имам предвид, когато казах, че?
Was habe ich meine, wenn ich das gesagt?
Това означава, каквото прави най-много разум в контекст, за да бъдем честни.
Es bedeutet, was auch immer das macht Sinn im Kontext, um ehrlich zu sein.
Ако имаме алгоритъм, на Процеси Strings-- ние сме вероятно
Wenn wir einen Algorithmus, der Prozesse Strings-- wir wahrscheinlich
говорим за размера на низа.
reden über die Größe der Zeichenfolge.
Ето данните set-- размера, броя
Das ist die Daten-Satz-- Die Größe, die Anzahl
на героите, които изграждат низа.
von Zeichen, aus denen sich die Schnur.
Ако ние говорим за един алгоритъм, който обработва файлове,
Wenn wir über ein Gespräch Algorithmus, der Dateien verarbeitet,
ние може да се говори за това как много килобайта съдържат този файл.
könnten wir darüber, wie sprechen viele Kilobytes umfassen diese Datei.
И това е набор от данни.
Und das ist der Datensatz.
Ако ние говорим за един алгоритъм който обработва масиви по-общо,
Wenn wir über einen Algorithmus im Gespräch daß Griffe Arrays allgemeiner
като алгоритми за сортиране или търсите алгоритми,
wie Sortieralgorithmen oder Suchalgorithmen,
ние сме най-вероятно става дума за броя на елементи, които съдържат масив.
Wir sind wahrscheinlich über die Anzahl Gespräche Elemente, die ein Array umfassen.
>> Сега, ние можем да се измери algorithm-- по-специално,
>> Jetzt können wir ein zu messen algorithm-- insbesondere
когато казвам, ние можем измерване на алгоритъм, I
wenn ich sage, wir können messen einen Algorithmus, I
означава да можем да се измери колко много ресурси, които то предприема нагоре.
bedeuten, können wir messen, wie viele Ressourcen nimmt es.
Дали тези ресурси са, колко байта RAM-- или мегабайта RAM
Ob diese Ressourcen sind, wie viele Byte RAM-- oder Megabyte RAM
тя използва.
es verwendet.
Или колко време е необходимо, за да работи.
Oder wie viel Zeit es braucht, um laufen.
И ние можем да наречем това измерване, произволно, е на п.
Und wir können diesen Aufruf zu messen, beliebig, f n.
Където п е броят на елементи в масива от данни.
Wobei n die Anzahl von Elemente in der Datenmenge.
И е на п е колко Нещо.
Und f n ist, wie viele Jährigen.
Колко единици ресурс прави тя изисква да обработват тези данни.
Wie viele Einheiten von Ressourcen funktioniert sie erfordern, um diese Daten zu verarbeiten.
>> Сега, ние всъщност не ми пука за това, което е на п е точно.
>> Nun, wir eigentlich egal über das, was f n ist genau.
В действителност, ние много рядко will-- със сигурност никога няма в тази class-- I
In der Tat, sehr selten will-- wir wird sicherlich nie in dieser class-- I
потопите в някоя наистина дълбоко анализ на това, което е на п е.
tauchen Sie ein in jeder wirklich tief Analyse, was f von n ist.
Ние просто ще говорим за това, което е на п е приблизително или това, което има тенденция да.
Wir sind gerade dabei, über das, was f sprechen n ungefähr oder was es dazu neigt.
И тенденцията на алгоритъм е продиктувано от най-високото си мандат ред.
Und die Tendenz eines Algorithmus ist von seinem höchsten Reihenfolge tige diktiert.
И ние можем да видим това, което съм кажеш с това, като се вземат
Und wir können sehen, was ich damit meine, indem sie
Един поглед към един по-конкретен пример.
einen Blick auf ein konkreteres Beispiel.
>> Така че нека да кажем, че имаме три различни алгоритми.
>> Also lassen Sie uns sagen, dass wir drei verschiedene Algorithmen.
Първият от който се п кубчета, някои единици ресурс
Von denen die erste dauert n in Würfel geschnitten, einige Einheiten der Ressourcen
да обработи набор данни от размера п.
um einen Datensatz der Größe n zu verarbeiten.
Ние имаме втори алгоритъм, който отнема п кубчета плюс п квадрат ресурси
Wir haben einen zweiten Algorithmus, der findet n hoch drei plus n quadriert Ressourcen
да обработи набор данни от размера п.
um einen Datensatz der Größe n zu verarbeiten.
И ние имаме една трета алгоритъм, който работи in-- че
Und wir haben ein Drittel Algorithmus, der in--, dass läuft
заема п кубчета минус 8п квадрат плюс 20 п единици ресурс
nimmt n gewürfelt minus 8n Quadrat plus 20 n Einheiten von Ressourcen
да обработва алгоритъм с данните, определени от размера на п.
einen Algorithmus zu verarbeiten, mit Datensatz der Größe n.
>> Сега отново, ние наистина не се случва да влязат в това ниво на детайлност.
>> Jetzt wieder, wir wirklich nicht gehen, in diesem Detailgrad zu erhalten.
Аз съм наистина просто трябва тези нагоре тук като илюстрация на точка
Ich bin wirklich nur noch diese bis hier als Illustration eines Punktes
че аз отивам да бъде вземане в секунда, което
daß ich werde sein was in einer zweiten, der
е, че ние само ми пука за склонността на нещата
ist, dass wir nur wirklich interessieren über die Tendenz der Dinge
като масивите от данни стават по-големи.
da die Datenmengen immer größer.
Така че, ако наборът данни е малък, има всъщност е доста голяма разлика
Also, wenn die Datenmenge ist klein, es gibt eigentlich ein ziemlich großer Unterschied
в тези алгоритми.
in dieser Algorithmen.
Третият алгоритъм има отнема 13 пъти по-дълго,
Der dritte Algorithmus gibt dauert 13 mal länger,
13 пъти размера на ресурсите, да тече по отношение на първия.
13-fache der Menge an Ressourcen, zu laufen, bezogen auf die erste.
>> Ако нашият набор от данни е размер 10, което е по-голям, но не е задължително огромен,
>> Wenn Sie unsere Datensatz Größe 10, die ist größer, aber nicht unbedingt riesig,
можем да видим, че има всъщност е доста голяма разлика.
können wir sehen, dass es eigentlich ein bisschen von einem Unterschied.
Третият алгоритъм става по-ефективно.
Der dritte Algorithmus wird effizienter.
Става дума за реално 40% - или 60% по-ефективен.
Es geht darum, tatsächlich 40% - oder 60% effizienter.
Това отнема 40% за период от време.
Es dauert 40% der Menge an Zeit.
Тя може да run-- може да отнеме 400 единици ресурс
Es kann run-- es dauern kann 400 Einheiten von Ressourcen
да обработва на набор от данни с размер 10.
um einen Datensatz der Größe 10 zu verarbeiten.
Като има предвид, първият алгоритъм, за разлика от това,
Während die erste Algorithmus hingegen
взема 1000 единици ресурс да обработва на набор от данни с размер 10.
nimmt 1.000 Einheiten von Ressourcen um einen Datensatz der Größe 10 zu verarbeiten.
Но вижте какво се случва, тъй като нашите номера стават още по-големи.
Aber schauen Sie, was passiert, als unsere Zahlen noch größer.
>> Сега, разликата между тези алгоритми
>> Nun wird die Differenz zwischen diesen Algorithmen
започнете да стане малко по-слабо забележими.
beginnen, etwas weniger deutlich.
А фактът, че има долния ред terms-- или по-скоро,
Und die Tatsache, dass es niedrigerer Ordnung terms-- oder besser gesagt,
условия с по-ниска exponents-- започнете да стане без значение.
Begriffe mit niedrigeren exponents-- starten irrelevant zu werden.
Ако един набор от данни е с размер 1000 и първата алгоритъм
Wenn ein Datensatz ist von der Größe 1000 und der erste Algorithmus
работи в един милиард стъпки.
läuft in eine Milliarde Schritte.
И вторият алгоритъм работи в един милиард и един милион стъпки.
Und der zweite Algorithmus läuft in eine Milliarde und eine Million Schritte.
И третият алгоритъм работи само срамежлив от един милиард стъпки.
Und der dritte Algorithmus läuft in knapp einer Milliarde Schritte.
Това е доста много милиард стъпки.
Es ist so ziemlich eine Milliarde Schritte.
Тези условия по-нисък ред започват да стане наистина неуместен.
Diese Terme niedrigerer Ordnung zu starten um wirklich irrelevant werden.
И само за наистина чук дома на point--
Und nur um wirklich hammer haupt die point--
ако въведените данни е с размер на million-- всички три от тях до голяма степен
Wenn der Dateneingang der Größe A million-- alle drei von ihnen ziemlich viel
вземете една quintillion-- ако ми по математика е correct-- стъпки
nehmen Sie eine quintillion-- wenn meine Mathe ist correct-- Schritte
за обработка на данни вход с размер на един милион.
mit einem Dateneingang zu verarbeiten der Größe einer Million.
Това е много стъпки.
Das ist eine Menge von Schritten.
А фактът, че един от тях може отнеме няколко 100,000, или двойка 100
Und die Tatsache, dass einer von ihnen könnte nehmen Sie ein paar 100.000 oder ein paar 100
още по-малко, когато милиона ние не говорим за редица
Millionen noch weniger, wenn wir über eine Reihe sprechen
че big-- това е вид без значение.
dass big-- es irgendwie irrelevant ist.
Всички те са склонни да вземат приблизително п кубчета,
Sie alle sind in der Regel übernehmen ca. n in Würfel geschnitten,
и така ние всъщност ще сезира на всички тези алгоритми
und so haben wir eigentlich beziehen würde Für alle diese Algorithmen
като по нареждане на п нарязан на кубчета или големи O на п кубчета.
als in der Größenordnung von n gewürfelt oder Big-O von n gewürfelt.
>> Ето списък на някои от по- общи изчислителни класове сложност
>> Hier ist eine Liste von einigen der mehr gemeinsame Komplexitätsklassen
че ние ще се сблъскате в алгоритми, като цяло.
dass wir stoßen in Algorithmen, in der Regel.
А също и по-специално в CS50.
Und auch speziell in CS50.
Те са поръчани от обикновено най-бързо в горната част,
Diese werden aus bestellt in der Regel am schnellsten an der Spitze,
да обикновено най-бавния в долната част.
allgemein langsamsten an der Unterseite.
Така постоянно време алгоритми са склонни да бъде най-бързият, независимо
So konstante Zeit-Algorithmen sind in der Regel die am schnellsten zu sein, unabhängig davon,
от размера на въвеждане на данни се преминава инча
von der Größe des Dateneingabe Sie übergeben in.
Те винаги да бъде в една операция или една единица от ресурси, за да се справят с.
Sie einem Arbeitsgang erfolgen immer oder eine Einheit von Ressourcen, zu beschäftigen.
Тя може да бъде 2, тя може да да бъде 3, може да е 4.
Es kann 2 sein, könnte es 3 sein, könnte es vier sein.
Но това е постоянно число.
Aber es ist eine konstante Zahl.
Той не се променя.
Sie ändert sich nicht.
>> Логаритмични алгоритми време са малко по-добро.
>> Logarithmischen Zeitalgorithmen sind etwas besser.
И наистина добър пример за логаритмична алгоритъм време
Und ein wirklich gutes Beispiel dafür, einen logarithmischen Algorithmus
вие със сигурност сте виждали до сега е най- Разкъсва на телефонния указател
Sie haben sicherlich inzwischen gesehen, ist die Auseinanderreißen des Telefonbuchs
да се намери Майк Смит в телефонния указател.
Mike Smith im Telefonbuch zu finden.
Ние намаляване на проблема на половина.
Wir schneiden das Problem in zwei Hälften.
И така, като п получава по-голям и по-големи и larger--
Und so, n größer wird und größer und larger--
Всъщност, всеки път, когато се удвои п, че отнема само още една стъпка.
in der Tat, jedes Mal wenn Sie verdoppeln n, dauert es nur noch ein Schritt.
Така че това е много по-добре отколкото, да речем, на линейното време.
Also das ist viel besser als, sagen wir, die lineare Zeit.
Което е, ако се удвои п, тя отнема двойно броя на стъпките.
Das ist, wenn Sie n verdoppeln, es nimmt die doppelte Anzahl von Schritten.
Ако се утрои п, това отнема утрои броя на стъпките.
Wenn Sie n verdreifachen, dauert es Verdreifachung der Anzahl der Schritte.
Една стъпка на един дял.
Einen Schritt pro Einheit.
>> След това нещата стават малко MORE- малко по-малко велик от там.
>> Dann wird es ein wenig more-- etwas weniger von dort super.
Имате линейно ритмично време, понякога наречена дневник линейното време или просто влезте п п.
Sie haben lineare rhythmische Zeit, manchmal genannt log lineare Zeit oder einfach nur n log n.
И ние ще пример на алгоритъм, който
Und wir werden ein Beispiel eines Algorithmus,
писти в п п дневник, който все още е по-добре от квадратното time-- п квадрат.
läuft in n log n, die noch besser ist, als quadratische Zeit-- n quadriert.
Или полином време, п двама всяко число по-голямо от две.
Oder polynomialer Zeit, n zwei beliebige Zahl größer als zwei ist.
Или експоненциално време, което е дори worse-- C до п.
Oder exponentieller Zeit, die Noch C bis worse-- der n.
Така че някои постоянен брой нараства на силата на размера на входа.
So angehoben einige konstante Anzahl die Leistung der Größe der Eingabe.
Така че, ако има 1,000-- ако въвеждане на данни е с размер 1000,
Also, wenn es 1,000-- wenn die Dateneingabe der Größe 1000,
това ще отнеме C до 1000-ната власт.
sie zur Preis 1000. Macht zu übernehmen C.
Това е много по-лошо от полином време.
Es ist viel schlimmer als Polynomialzeit.
>> Факториел време е още по-лошо.
>> Factorial Es ist noch schlimmer.
И в действителност, има наистина съществуват безкрайни алгоритми време,
Und in der Tat, es gibt wirklich tun existieren unendliche Zeit-Algorithmen,
като, така наречената глупаво sort-- чиято работа е да разбъркате случайно масив
wie beispielsweise so genannte dumme sort-- deren Aufgabe ist es, nach dem Zufallsprinzip Shuffle ein Array
и след това да се провери, за да видите независимо дали е сортирани.
und dann überprüfen Sie, ob es sortiert.
И ако това не е, на случаен принцип разбъркате масива отново
Und wenn es nicht, nach dem Zufallsprinzip mische das Array wieder
и проверка, за да се види дали това е сортирани.
und überprüfen Sie, ob es sortiert.
И както вероятно можете да imagine-- можете да си представите ситуация
Und wie Sie wahrscheinlich imagine-- können Sie können eine Situation vorstellen,
където в най-тежък случай, че волята всъщност никога не започнем с масива.
wobei im schlimmsten Fall, dass Wille nie wirklich mit dem Array zu starten.
Това алгоритъм би влязло завинаги.
Das Algorithmus würde ewig laufen.
И така, това би било безкрайна алгоритъм време.
Und damit wäre ein unendliche Zeit-Algorithmus.
Надяваме се, че няма да бъде написването всеки факторен или безкрайно време
Hoffentlich werden Sie nicht zu schreiben jede Fakultät oder unendliche Zeit
алгоритми в CS50.
Algorithmen in CS50.
>> Така че, нека да отнеме малко повече бетон разгледаме някои по-прости
>> Also, lassen Sie uns ein wenig mehr Beton Blick auf einige einfachere
изчислителни класове сложност.
Komplexitätsklassen.
Така че ние имаме един example-- или два примера here--
So haben wir eine example-- oder zwei Beispiele hier--
на постоянни алгоритми време, които винаги се вземат
der konstante Zeitalgorithmen, die immer nehmen
една операция в най-тежък случай.
eine einzige Operation in der Worst-Case.
Така че първото example-- имаме функция
So die erste example-- wir eine Funktion haben
наречена 4 за вас, които се масив с размер 1,000.
genannt 4 für Sie, die nimmt ein Array der Größe 1.000.
Но тогава очевидно всъщност не изглеждат
Aber dann offenbar nicht wirklich aussehen
най it-- не ми пука какво е вътре в него, на този масив.
bei es-- nicht wirklich, was ist innen von ihm, dieses Arrays.
Винаги се връща четири.
Immer nur liefert vier.
Така, че алгоритъм, въпреки факта, че тя
So, dass Algorithmus trotz der Tatsache, daß es
1000 се елементи не направя нещо с тях.
nimmt 1000 Elemente nicht nichts mit ihnen.
Просто се връща четири.
Nur gibt vier.
Той винаги е с една стъпка.
Es ist immer ein Schritt.
>> В действителност, добавете 2 nums-- които сме виждали преди, както well--
>> In der Tat, fügen Sie 2 nums-- die wir zuvor als well-- gesehen haben
Просто обработва две цели числа.
gerade verarbeitet zwei ganzen Zahlen.
Това не е една единствена стъпка.
Es ist nicht ein Schritt.
Това всъщност е няколко стъпки.
Es ist eigentlich ein paar Schritte.
Можете да получите, можете да получите б, можете да ги добавите заедно и може да отпечатва резултатите.
Sie erhalten ein, erhalten Sie b, Sie sie hinzufügen zusammen, und du Ausgabe der Ergebnisse.
Така че това е 84-стъпки.
So ist es 84 Stufen.
Но винаги е постоянна, независимо от или б.
Aber es ist immer konstant, unabhängig von a oder b.
Вие трябва да получите, да б, добавете ги заедно, продукция на резултата.
Du musst ein, bekommen b, fügen sie zusammen, das Ergebnis auszugeben.
Така че това е постоянен алгоритъм време.
Also das ist eine konstante Zeit-Algorithmus.
>> Ето един пример за линейното време algorithm--
>> Hier ist ein Beispiel für ein linearen Zeit algorithm--
алгоритъм, който gets-- че отнема една допълнителна стъпка, по възможност,
ein Algorithmus, der gets-- das braucht einen zusätzlichen Schritt, gegebenenfalls,
като вашия вход расте с 1.
wie Ihr Eingangs wächst um 1.
Така че, нека да кажем, че търсим номер 5 вътрешността на масив.
Also, sagen wir, wir suchen die Nummer 5 innerhalb eines Arrays.
Може да се наложи една ситуация, в която можете да намерите това доста рано.
Vielleicht haben Sie eine Situation, wo haben Sie ziemlich früh zu finden.
Но вие също може да има ситуация, в която
Aber Sie haben auch könnte eine Situation, wo es
може да е последният елемент от масива.
könnte das letzte Element des Arrays.
В масив от 5 размер, ако ние не търсим номер 5.
In einer Anordnung von der Größe 5, wenn wir sind für die Zahl 5 suchen.
Това ще отнеме 5 стъпки.
Es würde 5 Stufen.
И в действителност, представете си, че има Не 5 навсякъде в този масив.
Und in der Tat, sich vorstellen, dass es 5 nicht überall in diesem Array.
Ние все още действително трябва да разгледаме всеки един елемент от масива
Wir haben immer noch tatsächlich haben, zu betrachten Jedes einzelne Element des Arrays
за да се определи със или без 5 е там.
um zu bestimmen, ob oder ob nicht 5 ist da.
>> Така че в най-тежък случай, което е, че елементът е последен в масива
>> Also im ungünstigsten Fall, der das ist das Element in dem Array letzten
или не съществува изобщо.
oder überhaupt nicht existieren.
Ние все още трябва да разгледаме Всички N елементи.
Wir haben immer noch zu sehen alle der n Elemente.
И така, този алгоритъм работи в линейното време.
Und so dieser Algorithmus läuft in linearer Zeit.
Можете да потвърдите, че от екстраполиране малко с думите:
Sie können das bestätigen Extrapolation ein wenig mit den Worten:
ако имахме 6-масив и търсим номер 5,
wenn wir eine 6-Element-Array und wurden wir für die Zahl 5 suchen,
той може да отнеме 6 етапа.
sie treffen könnte, 6 Stufen.
Ако имаме 7-масив и ние не търсим номер 5.
Wenn wir eine 7-Elementanordnung und wir sind für die Zahl 5 suchen.
Може да отнеме 7 стъпки.
Es könnte dauern 7 Schritten.
Като прибавим още един елемент в нашия масив, това отнема още една стъпка.
Da wir ein weiteres Element hinzuzufügen, um unsere Array, dauert es noch ein Schritt.
Това е един линеен алгоритъм в най-лошия случай.
Das ist ein linearer Algorithmus im ungünstigsten Fall.
>> Двойка следните въпроси към вас.
>> Paar kurze Fragen für Sie.
Какво е това, което е runtime-- най-лошият време на работа
Was ist der runtime-- was ist das Worst-Case-Laufzeit
на този конкретен фрагмент от кода?
dieses bestimmten Code-Snippet?
Така че аз имам 4 линия тук, която работи от к е равна на 0, по целия път до м.
So habe ich eine 4-Schleife, die hier läuft von j gleich 0 ist, den ganzen Weg bis zum m.
И това, което аз виждам тук, е, че тялото на цикъла се изпълнява в константно време.
Und was ich hier sehen, ist, dass die Rumpf der Schleife läuft in konstanter Zeit.
Така че, като се използва терминология, ние вече говорихме какво about--
So mit der Terminologie, wir haben bereits about-- was gesprochen
ще бъде най-лошия случай по време на работа на този алгоритъм?
würde im schlimmsten Fall sein, Laufzeit dieses Algorithmus?
Вземете една секунда.
Nehmen Sie eine Sekunde.
Вътрешната част на контура работи в постоянна време.
Der innere Teil der Schleife läuft in konstanter Zeit.
И външната част на линия ще избяга м пъти.
Und der äußere Teil der Schleife wird sich m-mal ausgeführt.
Така че това, което е най-лошият време на работа тук?
Also, was ist das Worst-Case-Laufzeit hier?
Знаете ли, предполагам голям O на м?
Haben Sie Big-O von m erraten?
Вие искате да бъде прав.
Sie würden Recht haben.
>> Какво ще кажете за още една?
>> Wie wäre es mit einem anderen?
Този път ние имаме линия вътре в една линия.
Dieses Mal haben wir ein Schleife innerhalb einer Schleife.
Имаме външен контур която тече от нула до р.
Wir haben eine äußere Schleife das läuft von null auf p.
И ние имаме вътрешна линия, която работи от нула до р, и в това,
Und wir haben eine innere Schleife, die läuft von Null auf P, und im Inneren davon,
Заявявам, че тялото на линия минава в постоянна време.
Ich behaupte, dass der Körper die Schleife läuft in konstanter Zeit.
Така че това, което е най-лошият време на работа на този конкретен фрагмент от кода?
Also, was ist das Worst-Case-Laufzeit dieses bestimmten Code-Snippet?
Е, пак, имаме външен контур, която тече р пъти.
Nun, wieder haben wir ein äußere Schleife, die p-mal ausgeführt wird.
И всеки time-- итерация на тази линия, по-скоро.
Und jeder Iteration Zeit-- dieser Schleife statt.
Ние имаме една вътрешна линия че също работи стр пъти.
Wir haben eine innere Schleife dass auch läuft p Zeiten.
И тогава вътре в това, там е най- постоянно time-- малко фрагмент там.
Und dann im Inneren der, dass, gibt es das Konstante Zeit-- kleine Ausschnitt gibt.
>> Така че, ако имаме външен контур, че тече р пъти вътре от които е
>> Wenn wir also eine äußere Schleife, läuft p-mal innerhalb von denen ist
вътрешна линия, която тече р times-- това, което е
eine innere Schleife, läuft p times-- was
най-лошият време на работа на този фрагмент от кода?
das Worst-Case-Laufzeit dieser Code-Snippet?
Знаете ли, предполагам, че голяма-О р квадрат?
Haben Sie big-O p denke Quadrat?
>> Аз съм Дъг Лойд.
>> Ich bin Doug Lloyd.
Това е CS50.
Dies ist CS50.
Similar videos:

Computational Complexity
CS50
4.4K views 0 likes 0 dislikes 25 Oct 2017100% match

Recursion
CS50
45.1K views 0 likes 0 dislikes 13 Oct 201575% match










Arrays
CS50
41.2K views 121 likes 5 dislikes 07 Oct 201573% match










Operators
CS50
44.3K views 89 likes 4 dislikes 07 Oct 201573% match










Binary Search
CS50
128.6K views 0 likes 0 dislikes 26 Sep 201271% match










Breakfast in Singapore
Samuel and Audrey - Travel and Food Videos
78.7K views 880 likes 54 dislikes 01 Mar 201771% match

Loops
CS50
42.2K views 95 likes 2 dislikes 07 Oct 201571% match










Batu Caves tour and Indian food in Malaysia
Samuel and Audrey - Travel and Food Videos
27.8K views 350 likes 21 dislikes 07 Mar 201770% match

greedy
CS50
110.4K views 0 likes 0 dislikes 16 Sep 201369% match










Breakfast in Malaysia | Eating Roti in Kuala Lumpur
Samuel and Audrey - Travel and Food Videos
66.8K views 798 likes 33 dislikes 18 Mar 201769% match

CS50 Live, Episode 005
CS50
22.9K views 0 likes 0 dislikes 04 Apr 201469% match










Week 1, continued
CS50
94.4K views 0 likes 0 dislikes 12 Dec 201369% match










Self-Driving Cars
CS50
10K views 85 likes 5 dislikes 10 Nov 201569% match










Singapore Food Tour at a Hawker Centre on Old Airport Road
Samuel and Audrey - Travel and Food Videos
33.4K views 426 likes 24 dislikes 03 Mar 201769% match

MVC
CS50
7.1K views 57 likes 2 dislikes 02 Nov 201569% match










Week 4, continued
CS50
42.2K views 0 likes 0 dislikes 21 Oct 201468% match










PHP for Web Development
CS50
15.6K views 114 likes 5 dislikes 16 Jun 201668% match










Dynamic Memory Allocation
CS50
38.7K views 312 likes 4 dislikes 07 Oct 201568% match










Driving in India at Night in Crazy Traffic | Mumbai to Pune Road Trip
Samuel and Audrey - Travel and Food Videos
25.4K views 446 likes 24 dislikes 14 Dec 201867% match




暗黑高清版，米山和大菠萝同归于尽，地上装备是我的了
Uncle_Arcade82
21.6K views 196 likes 5 dislikes 10 Oct 202067% match

Data Types
CS50
61.8K views 185 likes 7 dislikes 07 Oct 201567% match










Hyundai i30N Hot Hatch Uphill Drive
zerotohundred
286.7K views 2.3K likes 247 dislikes 20 Aug 202067% match



CS50 Library
CS50
19.6K views 0 likes 0 dislikes 26 Sep 201267% match










双截龙，敌方小兵反水，你猜玛丽安用了什么手段
Uncle_Arcade82
5.2K views 72 likes 2 dislikes 01 Nov 202067% match

Dangers of Pesticides, Food Additives Documentary Film

54.7K views 112 likes 19 dislikes 30 Jun 201267% match











Merge Sort
CS50
38.2K views 180 likes 23 dislikes 07 Oct 201567% match










Data Structures Summary
CS50
13.8K views 0 likes 0 dislikes 19 Oct 201567% match










iOS App Development with Swift by Dan Armendariz
CS50
7.4K views 48 likes 3 dislikes 28 Jun 201666% match










20 Stunningly Beautiful English Idioms - English Vocabulary Lesson
English with Lucy
779.8K views 29.7K likes -1 dislikes 18 Sep 201966% match

Pune Food Tour! Foreigners trying Indian Sweets and Tandoori Chai in Pune, India
Samuel and Audrey - Travel and Food Videos
36.5K views 800 likes 29 dislikes 03 Jan 201966% match





Settings Privacy About Contact Donate