>> 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.