Bütün hüquqlar, belə ki, hesablama mürəkkəblik. Bir xəbərdarlıq yalnız bir az biz də far-- dalış əvvəl Bu yəqin ki, arasında olacaq ən math ağır şeylər biz CS50 haqqında danışmaq. Ümid edirəm ki, çox böyük olmayacaq və biz cəhd və sizə yardım olacaq prosesi, lakin ədalətli xəbərdarlıq bir bit. Bir az var riyaziyyat burada iştirak edir. Bütün hüquqlar, üçün belə etmək Bizim hesablama resurslarından istifadə real dünyada olan bu, həqiqətən var alqoritmlər anlamaq üçün vacibdir və necə data emal. Biz əgər həqiqətən səmərəli alqoritm, biz ehtiyatların məbləği minimuma endirmək olar biz ilə məşğul var. Biz bir alqoritm varsa ki, iş bir çox etmək niyyətindədir həqiqətən emal məlumatların böyük set, bu daha tələb edir daha çox vəsait, və məhsullarının pul, RAM, bütün növüdür. 

Belə ki, qadir olan bir analiz etmək alqoritm, bu alət dəsti istifadə edərək, əsasən, question-- soruşur bu alqoritm miqyaslı nə necə biz bunu daha çox məlumat atmaq kimi? CS50, biz data məbləği istəyirik ilə iş olduqca kiçik. Ümumiyyətlə, bizim proqramları gedir ikinci və ya less-- run yəqin ki, çox az xüsusilə erkən. 

Amma ki, məşğul olan bir şirkət haqqında düşünmək müştərilərin milyonlarla yüzlərlə ilə. Onlar emal etmək lazımdır ki, müştəri data. Müştərilərin sayı kimi, onlar var, böyük və daha böyük olur Bu tələb olacaq daha çox resursları. Necə bir çox resursları? Yaxşı ki, necə asılıdır biz alqoritm təhlil Bu Toolbox vasitələrdən istifadə. Biz mürəkkəbliyi haqqında danışmaq zaman bir alqoritm bəzən will Bu vaxt adlandırılacaq eşitmək mürəkkəbliyi və ya kosmik mürəkkəbliyi lakin biz yalnız olacaq complexity-- zəng etmək üçün biz ümumiyyətlə söhbət edirik ən pis ssenari. Mütləq pis qalaq verilir biz bunu atma bilər data, necə bu alqoritm gedir emal və ya data ilə məşğul? Biz, ümumiyyətlə, ən pis halda zəng bir alqoritm böyük O uzunluğu. Belə ki, bir alqoritm belə bilər kvadrat n və ya n O O axır. Haqqında və daha çox nə o ikinci deməkdir. 

Bəzən də, biz qayğı yoxdur yaxşı ssenari haqqında. Data hər şey, biz istədik olmaq və tamamilə mükəmməl idi və biz bu mükəmməl göndərilməsi edildi Bizim alqoritm vasitəsilə məlumatların seçin. Necə ki, vəziyyət idarə olardı? Biz bəzən kimi istinad böyük Omega, böyük O fərqli olaraq, belə ki, biz böyük Omega var. Ən yaxşı ssenariyə Big-Omega. Ən pis halda ssenari üçün Big-O. Ümumiyyətlə, biz zaman danışmaq bir alqoritm mürəkkəbliyi, bəhs edirik ən pis ssenari. Belə ki, nəzərə ki, saxlamaq. 

Bu sinif, biz ümumiyyətlə olacaq kənara ciddi təhlili tərk etmək. Elmlər və sahələri var Bu cür şeylər həsr olunmuş. Biz ağıl haqqında danışmaq zaman alqoritmlər vasitəsilə, biz çox parça-by-parça edəcəyik ki, alqoritmlər biz sinif haqqında danışmaq. Biz, həqiqətən, yalnız söhbət edirik ümumi mənada vasitəsilə əsaslandırıcı, Biz düsturlar, və ya dəlillər, ya kimi bir şey. Belə ki, narahat olmayın, biz olmayacaq böyük math sinif çevrilir. 

Belə ki, biz mürəkkəbliyi qayğı bildirib Bu sual, necə soruşur, çünki Bizim alqoritmlər böyük idarə edirsiniz və böyük data dəstləri onlara atılır. Yaxşı, bir data set nədir? Hesab edirəm ki, dedi mən nə demək idi? Bu ən edir nə deməkdir kontekstində mənada vicdanlı olmalıdır. Biz bir alqoritm varsa Prosesləri Strings-- biz yəqin edirik simli ölçüsü haqqında söhbət. Bu data var set-- ölçüsü, sayı simli etmək simvol. Biz söhbət edirik, əgər faylları emal alqoritm, biz necə söhbət ola bilər çox kilobayt fayl ibarətdir. Və data set var. Biz alqoritm bəhs edirsinizsə ki, ümumiyyətlə serialların emal Belə çeşidlənməsi alqoritmlərin kimi və ya alqoritmlər axtarış biz yəqin ki, sayı haqqında söhbət edirik bir sıra təşkil elementləri. 

İndi biz bir ölçmək bilər alqoritm, xüsusilə, Mən deyəndə biz Mən bir alqoritm ölçmək Biz necə ölçmək bilər deməkdir çox resursları onu edir. Bu resursları olsun, nə qədər RAM-- bir bayt və ya RAM megabayt Bu istifadə edir. Və ya nə qədər vaxt çalıştırmak üçün edir. Və biz bu zəng edə bilərsiniz n f, özbaşına, ölçmək. Harada n sayı data set elementləri. Və n f neçə somethings var. Neçə resurslarının kontur yoxdur bu məlumatların emal tələb edir. 

İndi biz, həqiqətən, qayğı yoxdur dəqiq n f nə haqqında. Əslində, biz çox nadir hallarda will-- əlbəttə ki, heç vaxt bu sinif I Hər hansı bir həqiqətən dərin dalış f n nə təhlili. Biz yalnız nə f haqqında danışmaq olacaq n təxminən ya nə üçün çalışır. Və bir alqoritm meyl edir yüksək order müddəti ilə diktə. Və biz nə edə bilərsiniz I alaraq ki, demək bir daha konkret misal oldu. 

Belə ki, biz var ki, deyək üç müxtəlif alqoritmləri. olan ilk n edir resursların kuşbaşı, bəzi bölmələri ölçüsü n data set emal. Biz alır ikinci alqoritm var Cubed plus n kvadrat resursları n ölçüsü n data set emal. Və biz bir üçüncü var ki in-- çalışır alqoritm tutur n Cubed minus 8n kvadrat resursların plus 20 n dənə bir alqoritm emal ölçüsü n müəyyən məlumatları ilə. 

İndi yenə, biz, həqiqətən niyyətində deyil detal bu səviyyəyə almaq. Mən yalnız bu qədər var həqiqətən alıram burada bir nöqtəyə bir illüstrasiya kimi Mən gedirəm ki, , ikinci edilməsi olan biz yalnız həqiqətən qayğı ki, şeyi tendensiya haqqında data dəstləri daha böyük almaq kimi. Data set kiçik Belə ki, var həqiqətən, olduqca böyük fərq bu alqoritmlər. orada üçüncü alqoritm 13 dəfə uzun çəkir Resurslarının 13 dəfə məbləği ilk bir nisbi çalıştırmak üçün. 

Bizim data set ölçüsü 10, əgər ki, , böyük, lakin mütləq böyük deyil biz orada olduğunu görə bilərsiniz həqiqətən bir fərq bir az. Üçüncü alqoritm daha səmərəli olur. Bu, həqiqətən, 40% haqqında - və ya 60% daha səmərəli. 40% vaxt məbləği alır. Bu bilər run-- bilər Resursların 400 ədəd ölçüsü 10 data set emal. Ilk Halbuki alqoritm, əksinə, resursların 1000 ədəd edir ölçüsü 10 data set emal. Amma nə baxmaq Bizim nömrələri daha böyük almaq. 

İndi fərq bu alqoritmlər arasında bir az daha az müəyyən olmağa başlayır. Var ki, və əslində aşağı sifariş şərtlərlə daha doğrusu, aşağı exponents-- ilə şərtləri qalxsın başlayın. Bir veri set ölçüsü əgər 1000 və ilk alqoritm bir milyard addımlar çalışır. İkinci alqoritm çalışır bir milyard və bir milyon addımlar. Və üçüncü alqoritm çalışır bir milyard addımlar yalnız utancaq olan. Bu olduqca çox bir milyard addımlar var. Həmin aşağı sifariş şərtləri başlamaq həqiqətən yersiz olmaq. Və yalnız həqiqətən ev hammer point data giriş ölçüsü a olduqda million-- bütün bunlar üç olduqca çox bir quintillion-- əgər almaq mənim riyaziyyat correct-- addımlar bir veri giriş emal ölçüsü bir milyon. Bu addımlar bir çox var. Və əslində onlardan biri bilər bir neçə 100,000 və ya bir neçə 100 milyon daha az zaman biz bir sıra bəhs edirik ki, bu cür yersiz var big--. Onlar bütün edirlər təxminən n Cubed, və biz, həqiqətən, həvalə edirəm bu alqoritmlərin bütün n qaydada olaraq Cubed və ya n Cubed böyük-O. 

Burada daha çox bəzi bir siyahısı ümumi hesablama mürəkkəblik dərsləri biz qarşılaşa bilərsiniz ki, alqoritmlər, ümumiyyətlə. Və həmçinin xüsusi CS50. Bu sifariş olunur ümumiyyətlə üst sürətli, altındakı ümumiyyətlə yavaş üçün. Belə ki, daimi vaxt alqoritmlər edirlər asılı olmayaraq, sürətli olmaq ölçüsü data giriş Siz keçir. Onlar həmişə bir əməliyyat və ya ilə məşğul resurslarının bir vahid. 2 ola bilər, güc 3 olmaq, 4 ola bilər. Amma bu, daimi sıra var. Bu fərqli deyil. 

Logaritmik vaxt alqoritmlər qədər yaxşıdır. Və həqiqətən yaxşı nümunə bir logarithmic vaxt alqoritm siz mütləq artıq görüldü etdik telefon kitab ayrı qoparmaq telefon kitab Mike Smith tapmaq üçün. Biz yarısında problem kəsdi. Və n daha böyük olur, belə ki, və daha böyük və larger-- əslində, hər zaman siz ikiqat n, yalnız daha bir addım atır. Ki, bir çox daha yaxşıdır, belə ki, daha demək, xətti vaxt. Siz n ikiqat əgər Hansı bu, addımlar sayı iki dəfə edir. Siz n üçqat, bu, davam edir addımlar sayı üç dəfə. Vahidi Bir addım. 

Sonra hər şeyi bir az more-- almaq az az böyük oradan. Siz bəzən xətti bədii vaxt log xətti vaxt deyilən və ya n log n. Və biz nümunə lazımdır bir alqoritm ki, hələ yaxşıdır n log n, çalışır daha kvadrat sýrada n kvadrat. Və ya çoxhədli dəfə, n iki Iki daha çox hər hansı bir sayı. Və ya exponential vaxt, hansı hətta worse-- C n edir. Belə ki, bəzi sabit sayı qaldırdı giriş ölçüsü gücü. Belə ki, əgər 1,000-- var, əgər data giriş, ölçüsü 1000 edir Bu 1000-ci hakimiyyətə C edəcək. Bu çoxhədli dəfə çox pis. 

Faktöryel vaxt daha pisdir. Və əslində, həqiqətən, orada nə sonsuz vaxt alqoritmlər var, kimin belə qondarma kimi axmaq sort iş təsadüfi bir sıra shuffle üçün və sonra kontrol olub sıralanır. Və bu təsadüfi deyil, əgər daha array shuffle və sıralanır olsun kontrol edin. Və yəqin ki, imagine-- bilər Siz bir vəziyyət təsəvvür edə bilərsiniz burada ən pis halda, bu iradə həqiqətən sıra ilə başlamaq heç vaxt. Bu alqoritm əbədi çalışır. Və belə ki, bir olardı sonsuz vaxt alqoritm. İnşallah yazılı olmayacaq Hər hansı bir faktöryel və ya sonsuz vaxt CS50 alqoritmləri. 

Belə ki, götürək bir az daha Bəzi sadə beton baxmaq hesablama mürəkkəblik dərsləri. Beləliklə, biz bir misal var və ya iki nümunələri burada daimi vaxt alqoritmlərin, olan həmişə almaq ən pis halda bir əməliyyat. Ilk misal Belə ki, biz bir funksiyası var , sizin üçün 4 adlanan ölçüsü 1000 bir sıra edir. Amma sonra yəqin həqiqətən baxmaq deyil pseudocode həqiqətən nə qayğı deyil at bunun daxili ki, serialın. Həmişə yalnız dörd qaytarır. Belə ki, alqoritm, bu, baxmayaraq ki, 1000 elementləri deyil edir onlara bir şey yoxdur. Yalnız dörd qaytarır. O, həmişə bir addım var. 

Əslində, 2 nums-- əlavə olan biz well-- əvvəl gördüm yalnız iki integers emal edir. Bu bir addım deyil. Bu, həqiqətən bir neçə addımlar var. Siz almaq, b almaq, onlara əlavə Birlikdə, siz çıxış nəticələri. Belə ki, 84 addımlar var. Lakin bu, həmişə sabit var asılı olmayaraq və ya b. Siz almaq lazımdır, b almaq, əlavə birlikdə onlara çıxış nəticəsidir. Belə ki, bir daimi vaxt alqoritm var. 

Burada bir misal var xətti vaxt alqoritm ki, edir gets-- alqoritm bir əlavə addım, bəlkə, Sizin input 1-artır kimi. Belə ki, biz aradığınız deyək bir sıra sayı 5 daxilində. Siz bir vəziyyət olduğu ola bilər Siz kifayət qədər erkən tapa bilərsiniz. Amma siz də ola bilər bir vəziyyət harada serialın son element ola bilər. Ölçüsü 5 bir sıra, əgər Biz sayı 5 aradığınız. 5 addımlar edəcək. Və əslində, var ki, təsəvvür Bu array deyil 5 yerdə. Biz hələ həqiqətən baxmaq serialın hər bir element müəyyən etmək üçün və ya 5 var. 

Belə ki, ən pis halda, element array son və ya bütün mövcud deyil. Biz hələ baxmaq lazımdır n elementləri bütün. Və bu alqoritm xətti vaxt çalışır. Siz ki, təsdiq edə bilər deyərək bir az apardığımızda, biz 6 element array idi əgər biz, sayı 5 aradığınız 6 addımlar bilər. Biz 7 element array var və Biz sayı 5 aradığınız. 7 addımlar bilər. Biz bir daha element əlavə olaraq array, bu daha bir addım edir. Ki, bir xətti alqoritm var ən pis halda. 

Cütlük üçün tez suallar. Nə runtime-- nədir ən pis halda uzunluğu kodu bu parçasını? Belə ki, çalışır, burada 4 loop var j 0, m-ə qədər bütün yol bərabərdir edir. Və nə mən burada görürəm, ki, loop bədən daimi vaxt çalışır. Belə terminologiya istifadə edərək biz artıq nə about-- söhbət etdik ən pis halda olardı Bu alqoritm uzunluğu? Ikinci edin. loop daxili daimi vaxt çalışır. Və xarici hissəsi loop m dəfə run gedir. Belə ki, ən pis halda runtime burada nə var? Siz m böyük O tahmin mi? Siz doğru olarıq. 

Necə başqa biri haqqında? Biz bu dəfə bir loop daxilində loop. Biz xarici loop var ki, sıfırdan p çalışır. Və biz çalışır daxili loop var sıfırdan p ki, daxilində, Mən dövlət orqanı olduğunu loop daimi vaxt çalışır. Belə ki, ən pis halda uzunluğu nə kodu bu parçasını? Bəli, yenə, biz var p dəfə çalışır xarici loop. Və hər sýrada iteration ki loop deyil,. Biz daxili loop var ki, p dəfə çalışır. Ki, daxilində Və sonra var orada daimi sýrada az parçasını. 

Biz xarici loop varsa Belə ki, olan daxili p dəfə çalışır daxili loop ki nə dəfə təkrar p çalışır ən pis halda uzunluğu kodu bu parçasını? Siz p böyük-O kare tahmin mi? 

Mən Doug Lloyd edirəm. Bu CS50 edir.