W porządku, więc, złożoność obliczeniowa. Wystarczy trochę ostrzeżenia Zanim zabierzesz się za far-- Prawdopodobnie będzie to m.in. rzeczy najbardziej matematyczne ciężki mówimy w CS50. Mam nadzieję, że nie będzie to zbyt przytłaczające a my postaramy i Cię w procesie, ale tylko trochę uczciwego ostrzeżenia. Jest trochę matematyki zaangażowanych tutaj. W porządku, więc w celu dokonania Korzystanie z naszych zasobów obliczeniowych w prawdziwym world-- to naprawdę ważne, aby zrozumieć algorytmy i jak przetwarzać dane. Jeśli mamy naprawdę efektywny algorytm, mamy Można zmniejszyć ilość zasobów mamy do dyspozycji, aby sobie z tym poradzić. Jeśli mamy algorytm, który zajmie dużo pracy przetwarzać naprawdę duży zestaw danych, to będzie wymagać więcej i więcej zasobów, które to pieniądze, pamięci RAM, wszystkie tego rodzaju rzeczy. 

Tak, jest w stanie przeanalizować Algorytm za pomocą tego zestaw narzędzi, w zasadzie, prosi question-- w jaki sposób ten skalę algorytmu jak rzucić więcej i więcej danych na nim? W CS50, ilość danych jesteśmy pracy z jest dość mały. Ogólnie rzecz biorąc, nasze programy będą uruchomić w drugim lub less-- prawdopodobnie o wiele mniej zwłaszcza na początku. 

Ale pomyśl o firmą, która zajmuje z setkami milionów klientów. I muszą przetwarzać że dane klienta. W miarę wzrostu liczby użytkowników, że mają coraz większe, to będzie wymagało coraz więcej zasobów. Jak wiele innych zasobów? Cóż, to zależy od tego jak analizujemy algorytmu, za pomocą narzędzi w przyborniku. Kiedy mówimy o złożoności algorithm-- które czasem będziesz usłyszeć to dalej czas Złożoność lub miejsca Złożoność ale my po prostu się zadzwonić complexity-- jesteśmy ogólnie mówić o scenariusz pesymistyczny. Biorąc pod uwagę najgorszego stos Dane że możemy być rzucając na niego, jak to jest algorytm będzie przetwarzać lub radzić sobie z tymi danymi? Zazwyczaj zadzwonić Najgorszy czas pracy algorytmu big-O. Więc algorytm można powiedzieć, aby uruchomić w O. N lub O n do kwadratu. I o tym, co te myśli w drugim. 

Czasem jednak, robimy opieki o najlepszym wypadku. Jeśli dane jest wszystko, co chcieliśmy że jest i to było absolutnie doskonałe i byliśmy wysłanie tego idealne zestaw danych za pośrednictwem naszego algorytmu. Jak radzi sobie w tej sytuacji? Czasami odnosi się do tego, jak big-Omega, więc w przeciwieństwie do big-O, mamy big-Omega. Big-Omega w najlepszym wypadku. Big-O w najgorszym scenariuszu. Ogólnie, gdy mówimy o złożoność algorytmu, mówimy o Najgorszy scenariusz. Miejcie to na uwadze. 

I w tej klasie, mamy na ogół dzieje opuścić rygorystyczną analizę bok. Istnieje nauki i pola poświęcony tego rodzaju rzeczy. Kiedy mówimy o rozumowaniu przez algorytmy, które zrobimy kawał-po-sztuki dla wielu Algorytmy mówimy w klasie. Jesteśmy naprawdę tylko o rozumowanie przez niego ze zdrowym rozsądkiem, nie z wzorami lub dowodów, lub coś podobnego. Więc nie martw się, nie będziemy zamienia się w wielki lekcji matematyki. 

Powiedziałem więc dbamy o złożoności dlatego, że zadaje pytanie, w jaki sposób Czy nasze algorytmy obsłużyć większe i Większe zestawy danych są wyrzucane na nich. Cóż, to, co jest zestaw danych? Co mam na myśli, kiedy powiedział, że? Oznacza to, co sprawia, że ​​większość sensu kontekście, aby być uczciwym. Jeśli mamy algorytm, na Procesy Strings-- jesteśmy prawdopodobnie mówi o wielkości napisu. To dane set-- wielkość, liczba znaków, które tworzą łańcuch. Jeśli mówimy o Algorytm, który przetwarza pliki, możemy mówić o tym, jak wiele kilobajtów zawierają ten plik. I to jest zbiór danych. Jeśli mówimy o algorytmie który obsługuje macierze bardziej ogólnie, takie jak algorytmy sortowania lub wyszukiwanie algorytmów, jesteśmy chyba mówić o liczbie Elementy, które zawierają tablicę. 

Teraz możemy zmierzyć algorithm-- w szczególności kiedy mówię, możemy pomiaru algorytm, ja oznacza, że ​​możemy zmierzyć jak wiele zasobów zajmuje. Czy te zasoby są, jak wiele bajtów RAM-- lub megabajtów pamięci RAM używa. Albo ile czasu potrzeba, aby uruchomić. I możemy nazwać pomiaru, arbitralnie, f n. Gdzie n oznacza liczbę elementy zestawu danych. F n jest to, jak wiele latków. Ile jednostek zasobów robi wymagać, aby przetwarzać te dane. 

Teraz, tak naprawdę to nie obchodzi o tym, co f n jest dokładnie. W rzeczywistości bardzo rzadko will-- Z pewnością nigdy nie będzie w tym class-- I nurkować w dowolnym naprawdę głębokie analiza tego, co f n. My tylko będziemy rozmawiać o tym, co f n jest w przybliżeniu lub co ma tendencję do. Tendencja algorytmu jest podyktowane najwyższym terminu zamówienia. I widzimy, co ja myśli, że biorąc Spojrzenie na bardziej konkretny przykład. 

Więc powiedzmy, że mamy trzy różne algorytmy. Z których pierwszy ma n pokrojone w kostkę, niektóre jednostki zasobów do przetwarzania zbioru danych o rozmiarze n. Mamy drugiego algorytmu, który n kostkę oraz n kwadratu zasobów do przetwarzania zbioru danych o rozmiarze n. I mamy trzeci algorytm, który działa in--, że zajmuje n kostkę minus 8n kwadratu plus 20 n jednostek zasobów do przetwarzania algorytmu z danymi zawartymi w rozmiarze n. 

Teraz znowu, tak naprawdę nie będzie dostać się do tego poziomu szczegółowości. Jestem naprawdę po prostu to się tutaj jako ilustracja punktu że będę co na sekundę, co jest to, że tylko naprawdę obchodzi o tendencji rzeczy jako zbiory danych stają się coraz większe. Więc jeśli zestaw danych jest niewielka, nie ma rzeczywiście dość duża różnica W tych algorytmów. Trzeci algorytm istnieje trwa 13 razy dłużej, 13 razy ilość zasobów uruchomić w stosunku do pierwszego. 

Jeśli nasz zestaw danych jest rozmiar 10, które jest większa, ale niekoniecznie duże, widzimy, że istnieje faktycznie trochę różnicy. W trzecim algorytmem staje się bardziej efektywny. Chodzi o to faktycznie 40% - lub 60% bardziej wydajne. To zajmuje 40% ilości czasu. To może run-- może potrwać 400 jednostek zasobów do przetwarzania zbioru danych o wielkości 10. Podczas gdy pierwsza Algorytm, przeciwnie, zajmuje 1000 jednostek zasobów do przetwarzania zbioru danych o wielkości 10. Ale zobacz, co się stanie, jak nasza liczba się jeszcze większe. 

Teraz różnica od tych algorytmów zaczynają się trochę mniej widoczne. A fakt, że istnieją niższego rzędu terms-- czy raczej, Terminy o niższym exponents-- zaczynają się nieistotne. Jeśli zestaw danych jest wielkości 1000 i pierwszy algorytm przebiega w ciągu miliardów stopni. A drugi algorytm działa w miliard i milion kroki. I trzeci algorytm działa w po prostu nieśmiały miliard kroków. To prawie miliard kroków. Warunki te niższego rzędu zacząć aby stać się naprawdę bez znaczenia. I tak naprawdę Młot do domu point-- jeśli dane wejściowe jest Rozmiar A million-- wszystkie trzy z nich dość dużo przyjmować jedną quintillion-- jeśli moja matematyka jest correct-- kroki przetwarzać dane wejściowe wielkości miliona. To jest dużo schodów. A fakt, że jeden z nich może potrwać kilka 100,000 lub kilka 100 jeszcze mniej, gdy mln mówimy o wielu że big-- to trochę bez znaczenia. Wszystkie one mają tendencję do około n pokrojone w kostkę, i tak byśmy rzeczywiście odnoszą wszystkich tych algorytmów jako na zlecenie n pokrojone w kostkę lub w big-O n sześcienny. 

Oto lista niektórych z bardziej Wspólne zajęcia złożoność obliczeniowa że uda nam się spotkać w algorytmy, na ogół. A także w szczególności w CS50. Są one uporządkowane od ogólnie najszybciej w górze ogólnie najwolniej na dole. Tak więc algorytmy stałym czasie tendencję być najszybszy, bez względu wielkości z wprowadzanie danych można przejść w. Oni zawsze mają jedną operację lub jedna jednostka zasobów do czynienia. To może być 2, to może za 3, może to być 4. Ale to stała liczba. Nie ulega zmianie. 

Algorytmy logarytmiczne czas są nieco lepsze. I naprawdę dobry przykład algorytm czasu logarytmiczna z pewnością widział pan już jest rozdzieranie książki telefonicznej znaleźć Mike Smith w książce telefonicznej. Tniemy problem w połowie. I tak jak n staje się większy oraz większe i larger-- w rzeczywistości, za każdym razem dwukrotnie n, to zajmuje tylko jeden krok. Więc to jest o wiele lepiej niż, powiedzmy, czas liniowy. Który jest, jeśli podwoi n, to ma podwójną liczbę kroków. Jeśli trzykrotnie n, trwa potroić liczbę kroków. Jeden krok za sztukę. 

Potem robi się trochę more-- trochę mniej wielkie stamtąd. Masz czas liniowy rytmiczne, czasem zwany dziennik czas liniowy lub po prostu n log n. A my przykładem o algorytm przebiega w n log n, która jest jeszcze lepiej niż kwadratowa time-- n do kwadratu. Albo wielomian czasu, n dwa każda liczba większa od dwóch. Albo wykładnicza czasu, który Jeszcze worse-- C do n. Tak więc niektóre stała liczba podniesiona do moc wielkości wejściowych. Tak więc jeśli jest 1,000-- jeśli Wprowadzanie danych jest wielkości 1000, zajęłoby C do 1,000th władzy. To dużo gorsze niż czasie wielomianowym. 

Silnia czas jest jeszcze gorzej. A w rzeczywistości, tak naprawdę nie istnieje nieskończona algorytmy czasowe, takie jak, tak zwane głupie sort-- którego zadaniem jest losowo przetasować tablicę a następnie sprawdzić, czy to klasyfikowane. A jeśli nie, losowo ponownie shuffle tablicę i sprawdzić, czy to jest klasyfikowane. I jak można prawdopodobnie imagine-- można wyobrazić sobie sytuację, gdzie w najgorszym przypadku, że wola nigdy nie zaczynają się od tablicy. Że algorytm będzie działać wiecznie. I tak, byłoby Algorytm nieskończony czas. Mam nadzieję, że nie będzie można pisać dowolny silnia lub nieskończony czas Algorytmy w CS50. 

Więc weźmy trochę więcej betonu spojrzenie na niektóre prostsze obliczeniowe klasy złożoności. Mamy więc example-- lub dwa przykłady here-- stałych algorytmów czasowych, które zawsze jednej operacji w najgorszym przypadku. Tak więc pierwszym example-- mamy funkcję nazywa 4 dla Ciebie, które ma tablicę wielkości 1,000. Ale najwidoczniej faktycznie nie wyglądają w it-- naprawdę nie obchodzi mnie, co jest wewnątrz niego, z tej tablicy. Zawsze po prostu zwraca cztery. Tak, że algorytm, Pomimo faktu, że zajmuje 1000 elementów nie zrobić coś z nimi. Po prostu zwraca cztery. To jest zawsze jeden krok. 

W rzeczywistości, dodać 2 nums-- które widzieliśmy wcześniej jako well-- tylko przetwarza dwie liczby całkowite. To nie jest jeden krok. Jest to tak naprawdę kilka kroków. Dostaniesz, masz b, można je dodać razem i jest drukowanie wyników. Więc to jest 84 kroków. Ale to jest zawsze stała, niezależnie od A lub B. Musisz dostać, dostać b, dodać je ze sobą, wyjście wynik. Więc to jest algorytm stała czasu. 

Oto przykład liniowa algorithm-- czas algorytm, który gets--, że trwa jeden dodatkowy krok, ewentualnie jako twój wkład rośnie o 1. Więc powiedzmy, że szukamy numer 5 w środku tablicy. Możesz mieć sytuację, w której może okazać się dość wcześnie. Ale może mieć również sytuacja, w której to może być ostatnim elementem tablicy. W tablicy 5, jeżeli rozmiar szukamy liczby 5. Zajmie to 5 kroków. A w rzeczywistości, wyobraź sobie, że nie ma nie 5 gdziekolwiek w tej tablicy. Nadal właściwie spojrzeć na każdy element tablicy W celu określenia czy 5 jest tam. 

Tak więc w najgorszym przypadku, który jest, że element jest ostatnia w tablicy lub nie istnieje w ogóle. Mamy jeszcze spojrzeć na wszystkie z n elementów. I tak ten algorytm działa w czasie liniowym. Możesz potwierdzić, że ekstrapolacji trochę, mówiąc: gdybyśmy mieli tablicę 6-elementów i szukaliśmy numerem 5, może to potrwać 6 kroków. Jeśli mamy tablicę 7-elementów i szukamy liczby 5. To może potrwać 7 kroków. Jak dodać jeden element do naszego tablica, to ma jeszcze jeden krok. To algorytm liniowy w najgorszym przypadku. 

Kilka szybkich pytań do Ciebie. Co się runtime-- co Najgorszy czas pracy tego konkretnego fragmentu kodu? Więc mam 4 pętlę tutaj, który działa z j jest równa 0, aż do góry do m. I co tu widzę, jest to, że Ciało pętli działa w stałym czasie. Tak więc używając terminologii mamy już rozmawialiśmy about-- co byłby najgorszy czas pracy tego algorytmu? Weź drugi. Wewnętrzna część pętli działa w stałym czasie. I zewnętrzną częścią Pętla ma zamiar uruchomić razy m. Więc co jest najgorszy czas pracy tutaj? Czy domyślasz big-O w m? Byłbyś w prawo. 

Jak o innym? Tym razem mamy pętli wewnątrz pętli. Mamy zewnętrzną pętlę który działa od zera do p. I mamy wewnętrzną pętlę, która działa od zera do P, jak i wewnątrz, że Oświadczam, że ciało Pętla działa w stałym czasie. Więc co jest najgorszy czas pracy tego konkretnego fragmentu kodu? Cóż, znowu mamy Zewnętrzna pętla, która prowadzi razy p. I każdy time-- iteracji z tej pętli, a. Mamy wewnętrzną pętlę które również prowadzi razy p. A następnie wewnątrz, że nie jest stała time-- mały urywek tam. 

Więc jeśli mamy zewnętrzna pętla prowadzi razy p wnętrze, które jest wewnętrzna pętla prowadzi p times-- to, co jest Najgorszy czas pracy tego fragmentu kodu? Czy domyślasz big-O p do kwadratu? 

Jestem Doug Lloyd. To CS50.