[Powered by Google Translate] [Seminar: Texniki Müsahibələr]
[Kenny Yu, Harvard Universiteti]
[Bu CS50 edir.] [CS50.TV]
Salam hər kəs, mən Kenny edirəm. Hal-hazırda kiçik öyrənilməsi kompüter edirəm.
, Mən keçmiş CS TF oldum və mən bir underclassman olanda mən bu idi arzulayıram
Mən bu seminar verirəm niyə və ki.
Belə ki, mən onu zövq ümid edirik.
Bu seminar, texniki müsahibələr haqqında
və bütün resursları, bu link əldə edə bilərsiniz
Burada bu link, ehtiyatların bir neçə.
Mən bir neçə problemlər, əslində, problemlərin bir siyahısını etdi.
Biz ipuçları tapa bilərsiniz Həmçinin ümumi ehtiyatları səhifə
müsahibə üçün hazırlamaq üçün necə,
Əgər faktiki müsahibə zamanı nə etməlidir haqqında məsləhətlər,
həmçinin gələcək sened üçün problemləri və ehtiyatları yaxınlaşmaq necə.
Bu, bütün online.
Və yalnız bu seminar, bir disclaimer, giriş üçün
bu kimi lazımdır - Sizin müsahibə hazırlıq
bu siyahı ilə məhdudlaşmır bilməz.
Bu yalnız bir guide deməkdir
və siz mütləq, mən duz bir taxıl ilə demək hər şey almaq lazımdır
həm də mən sizin müsahibə hazırlanmasında sizə kömək etmək üçün istifadə hər şey istifadə edin.
>> I növbəti bir neçə slaydlar vasitəsilə sürətləndirmək üçün gedirəm
biz faktiki Case əldə edə bilərsiniz.
Bir proqram engineering postion üçün müsahibə strukturu,
adətən 30 dən 45 dəqiqə,
şirkət olaraq çox el.
Tez-tez bir ağ board kodlaşdırma olacaq.
Belə ki, bu kimi, lakin tez-tez kiçik miqyaslı bir ağ board.
Bir telefon müsahibəsi qarşılaşdıqda, siz yəqin ki, istifadə edəcəyik
collabedit və ya Google Doc ya onlar sizin kodlaşdırma canlı görə bilərsiniz
Siz telefon müsahibə keçirilir etdiyiniz zaman.
Müsahibə özü adətən 2 və ya 3 problemləri
kompüter elm bilik test.
Və demək olar ki, mütləq kodlaşdırma iştirak edəcək.
Görürsünüz ki, sualların növləri adətən data strukturları və alqoritmlər var.
Və problemlər bu cür etməklə,
onlar kimi, xahiş edirik ki, nə zaman və məkan mürəkkəbliyi, böyük O nədir?
Tez-tez onlar da yüksək səviyyəli suallar,
belə bir sistem layihələndirilməsi
necə sizin kodu salınması olardı?
Nə interfeys, nə dərsləri, sizin sistem nə modulları var,
və bu necə birlikdə qarşılıqlı edirsiniz?
Belə data strukturları və alqoritmlər, həmçinin dizayn sistemi.
>> Biz Case üçün dalış əvvəl bəzi ümumi ipuçları.
Mən ən əhəmiyyətli qayda həmişə yüksək səslə düşünür ola düşünürəm.
Müsahibə sizin düşüncə prosesi off göstərmək üçün şans olması ehtimal edilir.
Müsahib ölçmek üçün müsahibə nöqtəsi
necə düşünürsünüz və necə bir problem keçir.
Edə bilərsiniz ən pis şey, bütün müsahibə boyunca ola səssiz edir.
Bu yalnız heç bir yaxşı.
Bir sual verilir, siz həmçinin sual başa əmin etmək istəyirəm.
Belə ki, öz sözləri ilə geri sual təkrar
və cəhd hərtərəfli bir neçə sadə test hallarda iş
Siz sual başa əmin etmək.
Bir neçə test hallarda vasitəsilə iş də bu problemi həll etmək üçün necə bir intuisiya verəcək.
Siz hətta bir neçə nümunələri siz bu problemi həll kömək tapmaq bilər.
Onların böyük tip incidir əldə edir.
Incidir almaq etməyin.
Müsahibələr çətin, lakin siz edə bilərsiniz ən pis şey,
səssiz olmaqla yanaşı, aşkar incidir edilir.
Siz Müsahib ki, təəssürat vermək istəmirəm.
Bir şey ki, - belə ki, bir çox insanlar, onlar müsahibə getmək zaman,
onlar, ilk ən yaxşı həll tapmağa cəhd
zaman, həqiqətən, bir glaringly Aşkar həll adətən var.
Bu yavaş ola bilər, bu səmərəsiz ola bilər, lakin yalnız göstərməlidir
yalnız belə daha yaxşı işləmək üçün bir başlanğıc nöqtəsi var.
Həmçinin, həll işarə baxımından yavaş
böyük O zaman mürəkkəbliyi və ya kosmik mürəkkəbliyi,
siz anlamaq ki, Müsahib nümayiş olunacaq
bu məsələlər kodu yazarkən.
Belə ki, ilk sadə alqoritmi ilə gəlmək qorxma
və sonra orada daha yaxşı işləyir.
Hər hansı sual, bu günə qədər? Okay.
>> Belə edək ilk problem dalış.
"N integers bir sıra nəzərə alaraq, array shuffles bir funksiya yazmaq
n integers bütün permutations bərabər güman ki, belə yerdə. "
Və mövcud bir təsadüfi tam generator var güman
yarısı üçündür, 0-dan i bir sıra bir tamsayı yaradır.
Hər kəs bu suala anlamaq varmı?
Mən sizə n integers bir sıra vermək, sizə shuffle onu istəyirik.
Mənim kataloqu, mən nə demək nümayiş bir neçə proqramları yazdı.
Mən, shuffle 20 elementlər bir sıra gedirəm
-10 ildən +9 üçün
və sizə bu kimi bir siyahı çıxış etmək istəyirəm.
Belə ki, bu mənim sıralanır giriş array və mən sizə shuffle onu istəyirik.
Biz bunu edəcəyik.
Hər kəs sual anlamaq varmı? Okay.
Belə ki, siz qalmışdır.
Bəzi fikirlər var? Siz n ^ 2, n log n, n kimi bunu edə bilərəmmi?
Təklif açın.
Okay. Emmy təklif Belə bir fikir,
ilk 0-dan 20-a təsadüfi sayı, təsadüfi tam, bir sıra hesablamaq edir.
Belə ki, bizim array 20 uzunluğu daşımır.
20 elementlər bizim sxemdə,
bu giriş array edir.
Və indi, onun təklif, yeni bir sıra yaratmaq
Bu çıxış array olacaq.
Və i Rand ilə geri əsasında -
i idi ki,, 17, deyək
ilk mövqeyi 17-ci element surəti.
İndi silmək lazımdır - biz burada bütün elementləri keçmək lazımdır
artıq biz sonunda bir boşluq və ortada heç bir deşik var.
İndi biz prosesi təkrar edin.
İndi 0 və 19 arasında yeni bir təsadüfi tam seçin.
Biz burada yeni bir i var və biz bu mövqeyi bu element surəti.
Sonra biz artıq maddələr keçmək və biz tam yeni array qədər biz prosesi təkrar edin.
Bu alqoritm run zaman nədir?
Yaxşı, bu təsiri hesab edək.
Biz hər bir element dəyişir.
Biz bu i aradan qaldırılması zaman, biz sola sonra bütün elementlər dəyişir.
Və bir O (n) dəyəri
çünki biz ilk element aradan əgər?
Belə ki, hər bir aradan qaldırılması üçün, biz aradan qaldırılması -
hər qaldırılması, bir O (n) əməliyyat götürür
biz kaldırma n yana, bu O (n ^ 2) shuffle gətirib çıxarır.
Okay. Belə ki, yaxşı bir başlanğıc. Yaxşı başlanğıc.
>> Digər bir təklif isə Knuth shuffle kimi tanınan bir şey istifadə etmək
və ya Fisher-Yates shuffle.
Və həqiqətən xətti vaxt shuffle var.
Və fikir çox oxşardır.
Yenə biz daxil array var
amma yerinə giriş / çıxış üçün iki seriallarda istifadə,
biz qarışdırılmış hissəsi takip serialın ilk hissəsi istifadə
və biz takip, sonra biz unshuffled hissəsi bizim serialın istirahət buraxın.
Belə ki, burada nə demək deyil. Biz başlamaq - biz bir i seçin
0-dan 20-bir sıra.
Bizim cari göstərici birinci index işarə edir.
Biz bəzi i burada seçmək
və indi dəyişdirmək.
Bu 5 idi və bu 4 Belə ki, əgər
nəticəsində array burada 5 burada və 4 olacaq.
İndi biz burada bir marker unutmayın.
Sol hər şey qarışdırılmış olunur
və sağ hər şeyi unshuffled olunur.
İndi biz prosesi təkrar edə bilərsiniz.
Biz indi 1 və 20 arasında bir təsadüfi index seçin.
Belə ki, i burada yeni güman edirlər.
İndi biz burada cari yeni mövqe ilə bu i dəyişdirmək.
Beləliklə, biz bu kimi geri və irəli dəyişdirmə yoxdur.
Mənə daha konkret etmək kodu getirsin.
Biz i bizim seçimi ilə başlamaq -
i 0 bərabər biz başlamaq, biz təsadüfi yeri j seçin
bu serialın unshuffled hissəsi, i, n-1.
Mən burada oldum Belə ki, burada və array qalan arasında təsadüfi index seçmək
və biz dəyişdirmək.
Bu shuffle sizin array üçün lazım olan bütün kodu.
Hər hansı sual?
>> Yaxşı, bir sual lazım, niyə bu doğru deyil?
Niyə hər permutation bərabər güman edir?
Və mən, bu sübut ilə getməyəcək
lakin kompüter çox problemləri induksiya vasitəsilə sübut edilə bilər.
Necə bir çox induksiya ilə tanış var?
Okay. Cool.
Belə ki, sadə induksiya bu alqoritm düzgünlüyünü sübut edə bilər
Sizin induksiya fərziyyə ola bilər yerləşir, güman
mənim shuffle hər permutation bərabər ehtimal qaytarır
qədər ilk i elementləri.
İndi, i + 1 düşünün.
Biz index j dəyişdirmək üçün seçin yolu ilə,
, sonra ətraflı işləmək - bu səbəb
Bu alqoritm qaytarır niyə ən azı bir tam sübut
bərabər ehtimal ehtimal hər permutation.
>> Bütün hüquqlar, növbəti problem.
Belə ki, "mənfi sıfır, postive integers bir sıra verilir
maksimum məbləği hesablayır bir funksiya yazmaq
daxil array hər hansı continueous subarray edir. "
Burada, məsələn, bütün nömrələri müsbət olduğu zaman,
sonra hazırda ən yaxşı seçim bütün array etməkdir.
1, 2, 3, 4, 10 bərabərdir.
Orada bəzi neqativ zaman,
Bu halda biz yalnız ilk iki istəyirəm
-1 və / və ya -3 seçilməsi bizim məbləğin aşağı gətirmək olacaq.
Bəzən biz serialın ortasında başlamaq ola bilər.
Bəzən biz heç bir şey seçə istəyirəm bir şey deyil yaxşı deyil.
Və bəzən, payız etmək daha yaxşıdır
sonra şey super böyük deyil. Belə ki, hər hansı bir fikir?
(Tələbə, anlaşılmaz) >> Bəli.
Mən -1 etmirlər düşünək.
Sonra da mən 1000 və 20,000 seçin
və ya yalnız 3 milyard seçin.
Yaxşı, ən yaxşı seçim bütün nömrələri iştirak edir.
Bu -1, mənfi olmasına baxmayaraq,
bütün məbləğ mən -1 etmək deyil, daha yaxşıdır.
Mən əvvəl qeyd ipuçlarını biri aydın aşkar etmək idi
ilk və brute force həlli.
Bu problem də brute force həlli nədir? Evet?
[Jane] Bəli, mən brute force həll edirəm
bütün mümkün birləşməsi (anlaşılmaz) əlavə olardı.
[Yu] Okay. Belə ki, Jane ideyası hər cür iştirak edir -
Mən paraphrasing Ben - hər mümkün davamlı subarray almaq üçün,
onun məbləği hesablamaq, sonra bütün mümkün davamlı subarrays maksimum edirlər.
Nə benzersiz mənim giriş array bir subarray müəyyən?
Nə iki şey lazımdır, kimi? Evet?
(Tələbə, anlaşılmaz) >> hüququ.
A aşağı göstərici və üst bound indeksi bağlı
benzersiz davamlı subarray müəyyənləşdirir.
[Qadın tələbə] Biz bu unikal ədəd bir sıra var qiymətləndirilməsi edirmi?
[Yu] No ona sual Beləliklə, biz array fərz edilir -
bizim array bütün unikal nömrə və cavab yoxdur.
>> Biz sonra brute force həlli, başlanğıc / son göstəriciləri istifadə edin
benzersiz bizim davamlı subarray müəyyənləşdirir.
Biz bütün mümkün start entries üçün təkrarlamaq Beləliklə, əgər,
və bütün son entries üçün> və ya = başlamaq və <n
siz məbləği hesablamaq, sonra biz bu günə qədər gördüm maksimum məbləği alır.
Bu aydın deyilmi?
Bu həll böyük O nədir?
Timewise.
Olduqca ^ 2 n deyil.
Biz 0-dan n təkrarlamaq Qeyd edək ki,
ki loop üçün biri.
Biz loop üçün demək olar ki, başdan başa başqa bir təkrarlamaq.
İndi ki, ərzində, biz, hər giriş yekunlaşdırmaq üçün
ki loop üçün bir var. Beləliklə, biz üç loops üçün iç içə, n ^ 3 var.
Okay. Bu başlanğıc nöqtəsi kimi gedir.
Bizim həll n ^ 3 daha pisdir.
Hər kəs brute force həll anlamaq varmı?
>> Okay. Daha yaxşı həll dinamik proqramlaşdırma adlı fikir istifadə edir.
Siz CS124 alsaq, bu, alqoritm və Data strukturu deyil
Bu texnika ilə çox tanış olacaq.
Və fikir, ilk kiçik problemlərin həlli yaratmaq üçün cəhd edir.
Başlanğıc ve bitiş: bu ilə nə demək, hazırda iki şey barədə narahat yoxdur.
Və bu annoying var. Biz bu parametrlərdən biri xilas ola bilər nə?
We're bizim orijinal problem alsaq, - bir fikir etmək
bir sıra hər hansı subarray maksimum məbləğ [O, n-1] tapa bilərsiniz.
Və indi biz cari index i, biz bilirik bir yeni subproblem var
biz orada bağlamaq lazımdır bilirik. Bizim subarray cari index da başa olmalıdır.
Qalan problem Belə ki, burada biz subarray başlamaq lazımdır?
Bu mənada edirmi? Okay.
Mən bu qədər kodlu etdik və nə deməkdir baxmaq edək.
Bu codirectory ildə subarray adlı proqram var
və bu maddələrin sıra edir
və mənim qarışdırılmış siyahısına maksimal subarray məbləğ qaytarılır.
Belə ki, bu halda, bizim maksimum subarray 3.
Və yalnız 2 və 1 istifadə edərək qəbul edir.
Nin yenidən run edək. Bu da 3 var.
Lakin bu dəfə biz 3 almışdır necə qeyd.
Biz etdi - biz yalnız 3 özü almaq
hər iki tərəfdən neqativ əhatə edir, çünki
məbləğində <3 getirecek.
10 maddələr üzrə run edək.
7 var Bu dəfə biz aparıcı 3 və 4 edirlər.
Bu dəfə 8, və biz 1, 4 və 3 alaraq ki almaq.
Belə ki, necə bir intuisiya vermək biz bu transformasiya problemi həll edə bilər,
bu subarray nəzər salaq.
Biz bu giriş array verilmiş və biz cavab 8 bilirik edirik.
Biz 1, 4, və 3 edirlər.
Amma biz həqiqətən ki, cavab var necə baxaq.
Nin bu göstəricilərin hər biri başa maksimal subarray baxaq.
Ilk mövqedə sona ki maksimal subarray nədir?
[Tələbə] Zero. >> Zero. Yalnız -5 etmirlər.
Burada həmçinin 0 olacaq. Evet?
(Tələbə, anlaşılmaz)
[Yu] Oh, sorry, bu -3 edir.
Bu 2-dir, belə ki, bu -3 edir.
Okay. Belə -4 ki, mövqe bitirmək üçün maksimal subarray nə
-4 olduğu? Zero.
Biri? 1, 5, 8.
İndi -2 olduğu yer üzrə son olmalıdır.
Belə ki, 6, 5, 7, və son bir 4.
Bu mənim entries ki, hər şeyi
Mən bu göstəricilərin hər bitmelidir olduğu transformasiya problem üçün,
sonra mənim final cavab yalnız, arasında sweep almaq
və maksimum edirlər.
Belə ki, bu halda 8 deyil.
Bu, maksimal subarray bu göstərici bitir o deməkdir ki,
və əvvəl bir yerdə başladı.
Hər kəs bu transformasiya subarray anlamaq varmı?
>> Okay. Yaxşı, bu üçün təkrar həyata rəqəm imkan verir.
Nin yalnız ilk bir neçə entries hesab edək.
Belə ki, burada, 8 0, 0, 0, 1, 5 idi.
Və sonra burada bir -2 idi ki, 6 yerə gətirdi.
Mən vəziyyəti giriş zəng əgər i subproblem (i)
necə bir əvvəlki subproblem cavab istifadə edə bilərsiniz
bu subproblem cavab?
Mən baxsaq, bu giriş, deyək.
Necə baxaraq cavab 6 hesablamaq olar
Bu array və bu serialın əvvəlki subproblems cavab birləşməsi? Bəli?
[Qadın tələbə] Siz xərclər array almaq
mövqeyi sağ əvvəl, 8 belə
və sonra cari subproblem əlavə edin.
[Yu], onun təklif bu iki ədəd baxmaq edir
Bu sayı və bu nömrəsini.
Beləliklə, bu 8 subproblem üçün cavab (1 - i) aiddir.
Və beni daxil array A. zəng edək
Mövqe i başa çatır ki, maksimal subarray tapmaq üçün,
Mən iki seçim var: mən ya subarray davam edə bilər
ki əvvəlki index başa çatıb, ya yeni bir sıra başlayın.
Mən əvvəlki göstərici ilə başlayan subarray davam olsaydı
sonra mən nail maksimum məbləği əvvəlki subproblem üçün cavab
üstəgəl cari array giriş.
Amma, mən də, yeni subarray başlayan seçim
bu halda məbləğ 0 deyil.
1, üstəgəl cari array giriş - Belə cavab 0 max, subproblem i edir.
Bu residiv mənada edirmi?
Bizim təkrar, biz yalnız aşkar kimi, subproblem i deyil
ki, əvvəlki subproblem maksimum plus mənim cari array giriş bərabərdir
olan əvvəlki subarray davam deməkdir
və ya 0, mənim cari index yeni subarray başlamaq.
Və bir dəfə biz final cavab sonra, həllər bu cədvəl tikilib,
yalnız subproblem array arasında xətti sweep etmək
və maksimum edirlər.
Bu yalnız nə dəqiq təzahürüdür.
Yəni biz yeni bir subproblem dizi, subproblems yaradır.
İlk giriş 0 və ya ilk giriş, bu iki maksimum ya edir.
Və subproblems qalan
biz yalnız aşkar dəqiq təkrar istifadə edin.
İndi bizim subproblems array maksimum hesablamaq və son cavab var.
>> Belə ki, necə çox yer biz bu alqoritm istifadə edir?
Yalnız CS50 qəbul etdik, onda çox yer müzakirə ola bilər.
Bəli, qeyd üçün bir şey ölçüsü n burada malloc adlı edir.
Ki, siz nə təklif edir?
Bu alqoritm linear space istifadə edir.
Biz daha yaxşı edə bilərəmmi?
Siz yekun cavab hesablamaq üçün lazımsız olduğunu qeyd edən bir şey var mı?
Hərhalda daha yaxşı sual olunur, nə məlumat
biz sonuna bütün yol keçirmək lazım deyil?
İndi biz bu iki xətləri baxsaq,
biz yalnız, əvvəlki subproblem qayğı
və biz yalnız biz heç belə uzaq gördüm maksimum qayğı.
Son cavab hesablamaq üçün biz bütün array ehtiyac yoxdur.
Biz son sayı, keçən iki ədəd yalnız lazımdır.
Maksimum üçün subproblem dizi, və son sayı üçün son sayı.
Belə ki, əslində, biz birlikdə bu loops fitil bilər
və xətti kosmosdan daimi yer gedin.
Kömək edib, bu günə qədər burada subproblem, bizim subproblem array rolu əvəz edir.
Belə ki, cari məbləği, bu günə qədər, əvvəlki subproblem cavab deyil.
Və edib, bu günə qədər bizim maks yer tutur.
Biz boyunca getmək kimi Biz maksimum hesablamaq.
Və biz, daimi məkanına linear space getmək
və biz subarray problemin həll xətti var.
>> Suallara bu cür bir müsahibə zamanı əldə edəcək.
Vaxt mürəkkəblik nədir; yer mürəkkəblik nədir?
Daha yaxşı edə bilərəmmi? Ətrafında saxlamaq lazımsız olan şeylər var?
Mən sizə öz almaq lazımdır ki, təhlillərini ön plana keçirmək bunu
Bu problemləri çalışırıq kimi.
Həmişə "Mən daha yaxşı edə bilərəmmi?", Özünüz xahiş edilə
Əslində, biz bu daha yaxşı edə bilər?
Bir oyun sual Sort. Sizə lazımdır, çünki Siz bilməz
ən azı problemin daxil oxuyun.
Lazımdır ki, ən azı problem üçün giriş oxumaq Beləliklə
siz, xətti zaman daha yaxşı edə bilməz deməkdir ki,
və daimi yer daha yaxşı edə bilməz.
Belə ki, bu, əslində, bu problemin ən yaxşı həlli.
Suallar? Okay.
>> Fond bazarı problemi:
"Müsbət, sıfır və ya mənfi n integers, bir sıra nəzərə alaraq,
ki, n gün ərzində fond qiyməti təmsil
Siz edə bilərsiniz maksimum mənfəət hesablamaq üçün bir funksiyası yazmaq
Bu n gün ərzində düz 1 fond alış-satış ki, verilmiş. "
Əslində, biz, aşağı almaq yüksək satış istəyirəm.
Və biz edə bilər yaxşı gəlir anlamaq istəyirəm.
Mənim tip geri gedir, nə dərhal aydın, sadə cavab, ancaq yavaş var?
Bəli? (Tələbə, anlaşılmaz) >> Bəli.
>> Beləliklə, siz yalnız baxmayaraq getmək və fond qiymətləri görünür
zaman hər bir nöqtəsi, (anlaşılmaz).
[Yu] Okay, belə ki, onun həlli - kompüter öz təklif
ən aşağı və ən yüksək hesablanması mütləq iş deyil
ən yüksək və ən aşağı əvvəl baş bilər, çünki.
Belə ki, bu problemin brute force həlli nədir?
Mən benzersiz mən etmək mənfəət müəyyən etmək üçün lazım olan iki şey var? Sağ.
The brute force həlli - oh, belə ki, Corc təklifini biz yalnız iki gün lazımdır
benzersiz bu iki gün mənfəəti birbaşa müəyyən etmək.
Belə ki, biz almaq / satmaq istədiyiniz hər cüt hesablamaq
mənfi və ya müsbət və ya sıfır ola biləcək mənfəət, hesablamaq.
Biz gün bütün cüt üzərində iterating sonra olun ki, maksimum mənfəət hesablamaq.
Yəni bizim final cavab olacaq.
Və həlli yoxdur, çünki, O (n ^ 2) olmaq n iki cüt seçmək olacaq -
siz son gün arasında seçə bilərsiniz ki, gün.
OK, belə ki, mən burada brute force həlli getmək niyyətində deyiləm.
Mən n log n həll olduğunu demək gedirəm.
Hal-hazırda n log n nə alqoritm bilirik?
Bu oyun sual deyil.
>> Sort Birleştirme. Birleştirme sort, n log n
və əslində, bu problemin həlli yollarından biri istifadə
adlı fikir birləşmə sort cür, ümumiyyətlə, bölmək və qalib.
Aşağıdakı kimi Və fikirdir.
Siz yaxşı alış hesablamaq / sol yarısında cüt satmaq istəyirik.
Yalnız iki gün ərzində ilk n, edə bilərsiniz ən yaxşı mənfəət tapın.
Sonra, ən yaxşı alış oompute / sağ yarısında cüt satmaq istəyirəm
iki gün ərzində belə son n.
İndi isə sual necə geri birlikdə bu həllərin birləşməsi yoxdur, var?
Bəli? (Tələbə, anlaşılmaz)
Okay. >> Mənə bir şəkil çəkmək imkan verir.
Bəli? (George, anlaşılmaz)
Məhz >>. George həll dəqiq hüququdur.
Onun təklif edir, birinci, ən yaxşı alış / satış cüt hesablamaq
və sol yarım baş ki, sol, sol zəng edək.
Best hüququ yarısında baş verir ki, cüt almaq / satmaq.
Biz yalnız bu iki ədəd müqayisədə Lakin biz işin itkin etdiyiniz
Burada almaq və sağ yarısında yerdə satmaq yerləşir.
Biz sol yarısında almaq, sağ yarısında satmaq.
Və həm yarıya indirir yayılır ki, ən yaxşı alış / satış cüt hesablamaq üçün ən yaxşı yol
burada minimum hesablamaq və burada maksimum hesablamaq üçün
və fərq edir.
Alış / satış cüt yalnız burada olduğu iki hallarda Belə ki,
yalnız burada, və ya hər iki yarıya indirir bu üç ədəd tərəfindən müəyyən edilir.
, Geri birlikdə bizim həllərin daxil etmək üçün bizim alqoritm Beləliklə
biz yaxşı alış / satış cüt hesablamaq istəyirəm
biz sol yarım almaq və sağ yarım satmaq yerləşir.
Və bunu ən yaxşı yolu, ilk yarısında ən aşağı qiymət hesablamaq üçün
ən doğru yarısında qiymət və fərq edir.
Ortaya çıxan üç mənfəət, bu üç ədəd, siz üç maksimum almaq
və bu ilk və son gün ərzində edə bilərsiniz ən yaxşı mənfəət var.
Burada mühüm xətləri qırmızı yerləşirsiniz.
Bu sol yarısında cavab hesablamaq üçün rekursiv çağırışdır.
Bu hüququ yarısında cavab hesablamaq üçün rekursiv çağırışdır.
Bu iki loops müvafiq olaraq, sol və sağ yarım üzrə min və max hesablamaq.
İndi mən, həm də yarıya indirir əhatə edən mənfəət hesablamaq
və yekun cavab bu üç maksimum deyil.
Okay.
>> Belə ki, əmin, biz bir alqoritm var, amma daha böyük sual
Bu zaman mürəkkəblik nədir?
Mən birləşmə cür qeyd səbəbi bu formada cavab bölmək ki,
iki və daha sonra geri birlikdə bizim həllərin birləşmə
dəqiq birləşməsi növ formasıdır.
Mənə müddəti ilə gedək.
Biz addımların sayı bir funksiyası t (n) müəyyən edin
n gün,
iki recursive zənglər
hər t (n / 2), başa gedir
və bu zənglər iki var.
İndi, sol yarısının minimum hesablamaq lazımdır
Mən n / 2 dəfə, üstəgəl sağ yarım maksimum nə bilər.
Belə ki, bu yalnız n.
Və sonra bir daimi iş plus.
Bu təkrarlanma tənliklər
dəqiq birləşməsi sort üçün təkrarlanma tənliklər edir.
Və biz bütün növ birləşmə n log n zaman bilirik.
Buna görə də, bizim alqoritmi də log n vaxt n.
Bu iteration mənada edirmi?
Bu yalnız qısa bir recap:
T (n) maksimum mənfəət hesablamaq üçün addımlar sayı
n gün ərzində.
Biz recursive zəng parçalanması yolu
, ilk n / 2 gün bizim həll zəng edir
ki, bir zəng, var
və sonra ikinci yarısında yenidən zəng.
Belə ki, iki zəng var.
Və sonra biz xətti vaxt edə bilərsiniz ki, sol yarısında bir minimum tapmaq
biz xətti vaxt edə bilərsiniz olan sağ yarısı maksimum tapa bilərsiniz.
Belə ki, n / 2 + n / 2 yalnız n.
Sonra biz hesab edirik kimi bəzi daimi iş var.
Bu təkrarlanma tənliklər dəqiq birləşməsi sort üçün təkrarlanma tənliklər edir.
Beləliklə, bizim shuffle alqoritm da n n daxil edin.
Belə ki, necə çox yer biz istifadə olunur?
Nin kodu geri edək.
>> Daha yaxşı bir sual, nə çox yığını çərçivəsində biz heç bir anda var olunur?
Biz recursion istifadə etdiyiniz ildən,
yığını çərçivəsində sayı bizim kosmik istifadə müəyyənləşdirir.
Nin n = 8 hesab edək.
Biz, 8 shuffle zəng
ilk dörd entries haqqında shuffle zəng edəcək
ilk iki entries bir shuffle zəng edəcək.
Belə ki, bizim yığını deyil - bu, bizim yığını deyil.
Və sonra biz, 1 təkrar shuffle zəng
və bizim əsas işi nədir, biz dərhal qayıtmaq.
Biz heç bu çox yığını çərçivəsində daha çox var?
No biz bir sehr etmək hər zaman olduğundan,
shuffle bir recursive sehr,
biz yarısında bizim ölçüsü bölmək.
Biz heç bir anda var yığını çərçivəsində maksimum sayı Beləliklə
log n yığını çərçivəsində əmri edir.
Hər bir yığını çərçivəsində daimi yer var
alan və buna görə də ümumi məbləği
biz heç istifadə sahəsi maksimum O (Giriş n) sahibidir
Ü n gün sayı.
>> İndi, həmişə özünüzü xahiş, "biz daha yaxşı edə bilərəmmi?"
Və xüsusilə də, biz artıq həll etdik bir problem bu azalda bilər?
A ipucu: yalnız əvvəl iki digər problemləri müzakirə, və shuffle olacaq deyil.
Biz maksimal subarray problem bu fond bazarında problem çevirə bilərsiniz.
Biz bunu edə bilər?
Əgər biri? Emmy?
(Emmy, anlaşılmaz)
[Yu] Exactly.
Maksimal subarray problem Belə ki,
biz davamlı subarray bir məbləğ üçün arıyorsanız.
Və səhmlərinin problem üçün Emmy təklifi,
dəyişikliklər və ya deltalar hesab edir.
Bu bir şəkil - Bu fond qiymət,
lakin biz hər ardıcıl gün arasında fərq etdi olduqda -
biz maksimum qiyməti maksimum mənfəət biz edə bilər ki
Burada almaq və burada satmaq əgər.
Amma nin davamlı baxaq - nin subarray problem baxaq.
Odur ki, biz edə bilər - burada burada gedən,
biz bir müsbət dəyişiklik var və sonra burada buradan gedən bir mənfi dəyişiklik yoxdur.
Amma sonra biz böyük bir müsbət dəyişiklik buradan burada gedir.
Bu bizim son mənfəət əldə etmək yekunlaşdırmaq istəyirəm ki, dəyişikliklər var.
Sonra daha çox mənfi dəyişikliklər burada var.
Bizim maksimal subarray problem bizim fond problem azaldılması üçün əsas
gün arasında deltalar hesab edir.
Belə ki, biz, deltalar adlı yeni array yaratmaq
, 0 olmaq üçün ilk giriş başlamaq
və sonra hər delta (i), fərq ki, qoy
mənim giriş array (i) və array (i - 1).
Sonra biz maksimal subarray üçün adi prosedur zəng
bir delta-nin array keçən.
Və maksimal subarray xətti vaxt, çünki
və bu azalma, bu delta array yaradılması bu prosesi,
da xətti dəfə
sonra səhmlər üçün yekun həlli O (n) iş plus O (n) iş hələ də O (n) əsəridir.
Belə ki, biz problemin xətti vaxt həll var.
Hər kəs bu transformasiya anlamaq varmı?
>> Həmişə var ki, ümumiyyətlə, yaxşı bir fikir
siz gördükdə yeni bir problem azaltmaq üçün cəhd edir.
Bir köhnə problem tanış görünür,
köhnə problem onu ​​azaldılması çalışırıq.
Və siz köhnə problem istifadə etdiyiniz bütün vasitələrdən istifadə edə bilər, əgər
yeni problem həll etsin.
Belə ki, bükmək üçün texniki müsahibələr çətin olunur.
Bu problemlər yəqin ki, daha çətin problemlər bəzi
Bir müsahibəsində görə bilərsiniz ki,
Mən yalnız əhatə edən bütün problemləri başa düşmürəm, əgər ki, tamam.
Bu daha çətin problemlər bəzi.
Təcrübə, təcrübə, təcrübə.
Mən sədəqə problemlər bir çox verdi, belə ki, mütləq o oldu.
Və müsahibələr uğurlar. Bütün ehtiyatları, bu link yerləşdirilir
və mənim böyük dostlarından biri, istehza texniki müsahibələr bunu təklif etdi
siz maraqlı etdiyiniz əgər, e-poçt e-poçt ünvanı Yao Will.
Bir sualınız varsa, mənə verə bilərsiniz.
Uşaqlar texniki müsahibələr bağlı konkret sual yoxdur
və ya biz bu günə qədər gördüm hər hansı bir problem?
Okay. Bəli, müsahibələr uğurlar.
[CS50.TV]