>> [მუსიკალური სათამაშო]
>> დევიდ ჯ Malan ყველა უფლება.
ასე რომ კეთილი იყოს უკან.
ეს არის CS50 და არის ბოლოს კვირაში სამი.
>> ასე იხსენებენ ამ ბოლო რამდენიმე კვირის განმავლობაში, ჩვენ ბევრი ხარჯვის საკმაოდ ცოტა
დროის C, პროგრამირებაში, on სინტაქსი.
და ეს სავსებით ნორმალურია, თუ თქვენ ჯერ კიდევ ბრძოლა პრობლემა Set 2, უნდა იყოს
banging თქვენი უფროსი წინააღმდეგ კედელზე.
ეს cryptic ლამაზი შეცდომის შეტყობინებები შეცდომებს, რომ თქვენ
ვერ საკმაოდ აყვანას ქვემოთ.
იმის გამო, რომ დანარჩენი დავრწმუნდი, რომ სულ რაღაც რამდენიმე კვირის "დრო თქვენ ვიხსენებთ
რამ, როგორიცაა კეისრისა და [? V-genair,?] შესაძლოა, ბზარი და
გააცნობიეროს, თუ რამდენად შორს თქვენ მოვიდა ამ მოკლე პერიოდში.
ასე რომ, თუ ეს რომელიმე ნუგეში, დევს იქ არის.
>> დღეს, თუმცა, ჩვენ ვიწყებთ გარდამავალ რამ უფრო მაღალ დონეზე.
და ჩვენ დავიწყებთ თავისთავად, რომ თქვენ ბიჭები ვიცი როგორ უნდა პროგრამას, ან
მინიმუმ დასაწყისი რომ კომფორტს დონეზე.
და ჩვენ დავიწყებთ განიხილავს, თუ როგორ შეგვიძლია წავიდეთ შესახებ შექმნასა პროგრამების მეტი
ეფექტურად.
როგორ შეგვიძლია წავიდეთ შესახებ ოპტიმიზაციის ეფექტურობის ჩვენი ალგორითმები და
ზოგადად გადაჭრის მეტი საინტერესო პრობლემები.
ხოლო დაწყებული უნდა თავისთავად, რომ თუ გვინდოდა, ჩვენ ვერ კოდი ნებისმიერი
მაგალითი გვაქვს გონება.
ასე რომ, დღეს, ჩვენ არ შეეხოთ keyboard ნებისმიერი სახით კოდი.
ეს იქნება ბევრად უფრო მაღალ დონეზე, და საბოლოო ჯამში, დაახლოებით პრობლემის გადაჭრაზე.
>> ასე რომ მიიღოს, რომ წერტილი, მინდა შესთავაზოს რომ შემდეგ შვიდი
ოთხკუთხედს წარმოადგენს შვიდი კარები, უკან რომლებიც მთელი bunch of
ნომრები, რომელთა შორის არის რიცხვი 50.
ნება მომეცით პროექტის ამ ამ ეკრანზე აქ ასევე.
და შესთავაზოს, რომ ჩვენ გვჭირდება მოხალისე, რათა დაგეხმაროთ me ნომერი შენობის წინ
ინტერნეტ აქ.
კარგით up, in ვარდისფერი.
ყველა უფლება.
რა არის შენი სახელი?
>> JENNIFER: [inaudible]
>> დევიდ ჯ Malan: უკაცრავად?
>> JENNIFER: Jennifer.
>> დევიდ ჯ Malan: Jennifer.
ყველა უფლება, ჯენიფერი.
კარგია თქვენთან შეხვედრა.
კარგით up.
ამიტომ აქ შვიდი კარები, და რა მინდა თქვენ ამის უფლება გვაქვს,
წინაშე ყველა თქვენი თანაკლასელები, არის ჩვენი ნომერი, 50.
იპოვოს ნომერი, შეგიძლიათ peek უკან ნებისმიერი ამ კარს უბრალოდ მოსმენების
ერთი კარები, და ეს გამოავლენს თავისი ნომერი.
და ვნახოთ, რამდენად სწრაფად თქვენ შეიძლება ჩვენი ნომერი, 50.
>> 15.
16.
50.
ლამაზად კეთდება.
ყველა უფლება.
რაუნდი ტაში for Jennifer.
>> [ტაში]
>> ყველა უფლება.
ასე რომ, რა იყო თქვენი სტრატეგია მოძიებაში ნომერი, 50?
>> JENNIFER: Um, ვფიქრობდი, იქნებ, თუ -
[Inaudible]
>> დევიდ ჯ Malan: Oh.
მისთვის ერთი მეორე.
ასე იყო თქვენი სტრატეგია მოძიებაში ნომერი, 50?
>> JENNIFER: ასე რომ მე მხოლოდ იწყება დაწყებული, თუ რას პირველი ნომერი
იყო, და მერე ვიფიქრე, იქნებ, თუ ისინი დახარისხებული, მე მხოლოდ შენარჩუნება
მოსმენების უმაღლესი up?
>> დევიდ ჯ Malan: OK.
და ჩვენ, როგორც ჩანს, არ ი რომ იყოს საქმე.
მიუხედავად იმისა, რომ, მოდით, კანი უკან ფენების უბრალოდ ცოტა და მინდა
წინ და გამოვლენა სხვა კარი თქვენ ვერ ავირჩიეთ?
>> JENNIFER: Oh, ძვირფასო.
>> დევიდ ჯ Malan: Ah.
>> JENNIFER: ასე რომ უბრალოდ მიიღო გაუმართლა.
>> დევიდ ჯ Malan: ასე რომ შენ გაუმართლა.
ყველა უფლება.
ასე რომ ცუდი არ არის.
მაგრამ ეს საინტერესო რისთვისაც, არა?
თუ თქვენ აიღო და გააკეთეთ მისაღებად, მართლაც, ცოტა გაუმართლა არსებობს.
მაგრამ თუ თქვენ ვივარაუდოთ, რომ ნომრები დახარისხებული, შეგიძლიათ უფრო ზუსტად
თუ როგორ, რომ გავლენა მოახდინა თქვენი საქციელი?
>> JENNIFER: ასე რომ თუ ისინი დახარისხებული, I ეგონა, შესაძლოა, პატარა რომ ყველაზე დიდი.
>> დევიდ ჯ Malan: OK.
>> JENNIFER: ან თუ ეს დასრულდა მიმდინარეობს მართლაც დიდი, მაშინ უდიდეს რომ პატარა.
>> დევიდ ჯ Malan: OK.
ასე რომ, ყველაზე დიდი, რომ ყველაზე პატარა, ან პატარა რომ ყველაზე დიდი.
მაგრამ ნება მიბოძეთ შესთავაზოს, ვარაუდობენ, თქვენ ჰქონდა მიღებული უბედური, და ვარაუდობენ, რომ ისინი
არ იყო, ფაქტობრივად, დალაგებულია, რამდენი იმ კარს, შესაძლოა, თქვენ არ მოუხდა peek
უკან რომ უარეს შემთხვევაში?
>> JENNIFER: ყველა მათგანი.
>> დევიდ ჯ Malan ყველა მათგანი.
მოდით განზოგადება, რომ როგორც ო.
არსებობს ხდება, რომ 7, ​​მაგრამ უფრო ზოგადად ამბობენ, რომ არსებობს n კარი
ეკრანზე აქ.
ასე რომ, უარეს შემთხვევაში, თქვენ უნდა თვალი უკან 7 კარები, ან ო კარი.
ასე რომ, ეს ნამდვილად არის, ეს ცოტა გისურვებთ დღეს, მაგრამ ეს ნამდვილად წრფივი
ალგორითმი სახის, მიუხედავად იმისა, რომ თქვენ იყო ასეთი skipping გარშემო.
ის არის, რომ სამართლიანი?
>> JENNIFER: ჰო.
>> დევიდ ჯ Malan: პირველ რიგში, ნება მომეცით, რომ თქვენი სტრატეგია ცვლილებები თუ მე გადაადგილება us to
ჩვენი მეორე მაგალითი აქ 7 სხვადასხვა კარები.
ისეთი რაოდენობით, მაგრამ ეს დრო ისინი დახარისხებული.
რა არის თქვენი სტრატეგიის აქ იქნება, ცდილობს დააყენა თქვენი გონება რა
რა ნომრებზე იყო -
>> JENNIFER: OK.
>> დევიდ ჯ Malan: - ადრე?
>> JENNIFER: დავიწყოთ პირველი ერთი.
>> დევიდ ჯ Malan ყველა უფლება.
დაწყება პირველი.
4.
ახლა, თუ სად აპირებს წავიდეს, და რატომ?
>> JENNIFER: 4 მართლაც პატარა.
ასე რომ, თუ ისინი ერთგვარი იქნებ პატარა to ყველაზე დიდი, უნდა
იყოს ორჯერ, რომ და -.
>> დევიდ ჯ Malan: OK.
ვნახოთ, რომელიც, თქვენი აზრით?
>> JENNIFER: სცადეთ ბოლო.
ლამაზი.
>> დევიდ ჯ Malan: ძალიან ლამაზად კეთდება.
ყველა უფლება.
>> [ტაში]
>> დევიდ ჯ Malan: OK.
ასე რომ თქვენ რეალურად აკეთებს ამ horribly, იმიტომ, რომ თქვენ
ამის ძალიან კარგად.
რომელ გვიტოვებს ვერ გარკვეული რაოდენობა.
მოდით ცდილობენ გააფართოვოს უკან აქ.
>> JENNIFER: OK.
>> დევიდ ჯ Malan: ძალიან კარგად კეთდება, მაინც.
ასე რომ დაიწყო თავიდან, თქვენ ნახეთ, რომ ეს იყო 4, მაშინ
გადავიდა ბოლომდე.
თუმცა ვარაუდობენ, თქვენ ვერ გაუმართლა არსებობს და ვარაუდობენ, 50
იყო სხვაგან.
რა თქვენი მესამე ნაბიჯი იქნებოდა?
>> JENNIFER: დაბრუნება დასაწყისში.
>> დევიდ ჯ Malan: დაბრუნება დასაწყისში.
OK, ასე რომ თქვენ, რომ მე შეეხო ეს კარი, რომელიც 8.
ყველა უფლება.
ასე რომ, ეს არ არის 50.
სად იქნებოდა თქვენ არ ჩანდა შემდეგი?
>> JENNIFER: თუ არ იცოდნენ, რომ გადანაწილებული.
>> დევიდ ჯ Malan: სწორი.
კარგად, თუ იცოდნენ ისინი დახარისხებული -
>> JENNIFER: Oh, იცოდნენ, ჰო.
>> დევიდ ჯ Malan: - მაგრამ თქვენ არ ვიცი, სადაც 50 იყო კიდევ?
>> JENNIFER: უბრალოდ შენარჩუნებას აპირებს.
>> დევიდ ჯ Malan ყველა უფლება.
OK.
შენარჩუნებას აპირებს.
კარგი, რომ შემიძლია მუშაობა.
>> JENNIFER: OK.
>> დევიდ ჯ Malan: ახლა კი, თუ უბრალოდ მიმდინარეობს შენარჩუნებას აპირებს, რა არის თქვენი
ალგორითმი devolving მხარს უჭერს შევიდა.
>> JENNIFER: წრფივი -.
>> დევიდ ჯ Malan: ეს არის ერთგვარი წრფივი.
მაგრამ ნება მიბოძეთ შესთავაზოს, ნება მიბოძეთ ადგილზე.
ნება მომეცით ცარიელია გვერდზე.
იგივე რაოდენობა, იმავე მოწყობა, იგივე კარები.
მაგრამ ვფიქრობ უკან რომ პირველი დღე კლასში როდესაც ჩვენ დახიეს ტელეფონი წიგნი
ნახევარი, სახის, და რა იყო ჩვენი სტრატეგია იქ?
>> JENNIFER: დაწყება შუა.
>> დევიდ ჯ Malan: OK.
ასე იწყება ცენტრიდან.
მოდით წავიდეთ წინ და გამოსცადეთ, რომ.
დაწყება შუა მიერ გამოვლენის, რომ კარი.
ასე რომ, ნომერი 16.
მაინც რაში ძლიერი ბიჭი არ კეთდება, ვინც გაწყვიტა სატელეფონო წიგნი ნახევარი,
მიიღოს მომდევნო ვხვდები?
>> JENNIFER: გადადით ამ ნახევარი.
>> დევიდ ჯ Malan: და რატომ უნდა არა?
>> JENNIFER: თუ ისინი ერთგვარი პატარა to ყველაზე დიდი, მაშინ 50 უნდა იყოს
იმ ბოლომდე.
>> დევიდ ჯ Malan: გარემონტებული.
სრულიად საფუძვლიანია.
ასე რომ, ისევე როგორც სატელეფონო წიგნი, წასვლა მარჯვენა განსხვავებით მარცხენა, მაგრამ აქ
მთავარი takeaway.
თქვენ შეგიძლიათ გადაყარეთ, ან გაანადგურეს off, ნახევარი ეს პრობლემა, რის გამოც თქვენ არ
7 კარს, მაგრამ რეალურად მხოლოდ 3.
რომელ დაახლოებით ნახევარი ზომის პრობლემა.
ყველა უფლება.
ასე რომ, ახლა, რას აქვს შემდეგ გაკეთდა თქვენ წავიდეთ უფლება?
>> JENNIFER: ასე 16 ჯერ კიდევ საკმაოდ პატარა, შედარებით 50, იქნებ ვეცდები,
ისევე, როგორც ეს ერთი.
>> დევიდ ჯ Malan ყველა უფლება.
42.
ყველა უფლება, ასე რომ, ახლა რა არის თქვენი ინსტიქტი გეუბნებით?
>> JENNIFER: მე ვერ გადააგდებს ამ და შემდეგ უბრალოდ -
>> დევიდ ჯ Malan: OK.
კარგი, შეგიძლიათ გადაყარეთ მარცხენა ნახევარში არსებობს.
>> JENNIFER: - გააშუქა ეს ერთი.
>> დევიდ ჯ Malan: და მარჯვნივ.
>> JENNIFER: ჰო.
>> დევიდ ჯ Malan: ასე რომ მიუხედავად იმისა, რომ ეს რთული სანახავად ალბათ, როდესაც იქ მხოლოდ
7 კარები, ვიფიქროთ, ახლა, რესურესების
ალგორითმი უბრალოდ გამოყენებული.
In წინა შემთხვევაში, გააკეთეთ მიიღეთ გაუმართლა, რომელიც დიდი.
მაგრამ თქვენ ამაზე გამოყენება heuristic, მე ვიტყოდი.
გამოყენებულია სახის თქვენი ინსტინქტები და იცის ეს გადანაწილებული, თუ ეს საკმაოდ
მცირე დასაწყისში, ბუნებრივია, ჩვენ მივიღე წასვლა უფრო მარჯვნივ.
მაგრამ გარკვეული, თქვენ მიიღო გაუმართლა, იმიტომ, რომ, შესაძლოა, ეს იყო ნომერი 100,
და შესაძლოა 50 უფრო ცენტრიდან.
იქნებ 50 კიდევ მეტი აქ.
>> მაგრამ რა გააკეთეთ თქვენ ცოტა განსხვავებულად ამ დროს იყო, გააკეთეთ იგივე
ისევ და ისევ.
და მე ამტკიცებენ, რომ რა უბრალოდ საერთოდ, თუმცა გავლენა მოახდინა ტელეფონი
წიგნის მაგალითად, რაღაც ბევრად მეტი ალგორითმული, და ბევრი
ნაკლებია, სპეციალური cased.
გაცილებით ნაკლებია instinctive.
ასე რომ, დღის ბოლომდე, როგორ თქვენ აღწერს ეფექტურობის
პირველი ალგორითმი, სადაც თქვენ წავიდა მარცხნიდან მარჯვნივ, წინააღმდეგ
მეორე ალგორითმი აქ?
>> JENNIFER: ეს უნდა, ისევე როგორც, შესაძლოა, HALVE დროს, ან კიდევ უფრო, ჰო.
>> დევიდ ჯ Malan: OK, შესაძლოა კიდევ უფრო.
მოდით დააყენებს ცოტა რთული, რომ.
რა, თუ ჩვენ გავაგრძელებთ ამ ლოგიკა, ჩვენ ნამდვილად განახევრდა
გაშვებული დროის ამ მეორე ალგორითმი მიერ სროლა მოშორებით ნახევარში
ნომრები, მაგრამ რა მივიღეთ ამის გაკეთება მომდევნო iteration, როდესაც Jennifer გამოვლინდა
მეორე ნომერი?
>> ჩვენ განახევრდა ნომრები კარი ერთხელ.
და მაშინ რა მივიღეთ გააკეთებს მას შემდეგ, თუ აქ იყო უფრო კარ თამაში?
ჩვენ გვინდა HALVE მათ, და კიდევ ერთხელ, და ისევ, და ისევ.
და ეს იყო, ისევე, როგორც თქვენ ბიჭები ყველა იდგა up პირველ კვირას
კლასი, ნახევარი თქვენ მაგიდასთან დაჯდომა, ნახევარი თქვენგანს დაჯდომა, ნახევარი თქვენგანი
დაჯდომა, სანამ ერთ მარტოხელა სულის იდგა.
და ჩვენ ვთქვით, რომ გაშვებული დრო ის, რომ მთელი რიგი ზომების დასჭირდა იყო
ბრძანებით, თუ რა?
>> დინამიკები 1: [inaudible]
>> დევიდ ჯ Malan: ასე ჟურნალი ბაზა -2 n, ან უბრალოდ უფრო მარტივად, შესვლა of ო.
ასე რომ რაღაც ლოგარითმული.
ხოლო გრაფაში არ იყო სწორი ხაზი აღვნიშნავ, რომ დამძიმდა და უარესი, ეს იყო
ამ საინტერესო მრუდი რომ არ მიიღეთ ისე ცუდია დროთა განმავლობაში.
მოდით გამართავს შესახებ, რომ ამ იდეას.
მოდით მადლობა გადავუხადო Jennifer.
მადლობა იმდენად მომავალი up.
ხოლო, ერთი წ.
არ სამაგიდო ნათურები დღეს, მაგრამ ჩვენ გვაქვს CS50 სტრესი ბურთები.
>> JENNIFER: Yay.
>> დევიდ ჯ Malan: ყველა უფლება, აქ.
მადლობას გიხდით ხარჯების სტრესი აქ.
ყველა უფლება.
მოდით ვნახოთ, შევძლებთ თუ არა ახლა formalize ამ ცოტა მეტი.
ასე რომ, კიდევ ერთხელ, რაც ჩვენ გავაკეთეთ იყო არსებითად იგივე როგორც ჩვენ გავაკეთეთ
ამ პირველ კვირას.
მაგრამ ვიდრე ბოლომდე მხოლოდ წრფივი ალგორითმი, რომელიც ჩვენ გამოსახული
ადრე, როგორც ეს სწორი ხაზი, რომლის დროსაც, თუ ჩვენ კიდევ ერთი კარი
ეკრანზე, და Jennifer აკეთებთ არ უნდა გამოიყურებოდეს, პოტენციურად,
უკან კიდევ ერთი კარი.
თუ ჩვენ კიდევ ორი ​​კარი, მან შეიძლება ჰქონდეს თვალი უკან კიდევ ორი ​​კარი.
>> ასე რომ, იყო ამ წრფივი შორის ურთიერთობა ზომის
პრობლემა, ვთქვათ, x-ღერძი და დროის სჭირდება
მოგვარება on წ.
მაგრამ სურათს მე alluding to ადრე იყო ეს მწვანე ზოლში.
მწვანე შეგნებულად, რადგან ეს მხოლოდ იყო.
თეორიულად, ალგორითმი, როდესაც ჩვენ ეს გავაკეთეთ ერთად სატელეფონო წიგნი, როცა ჩვენ ეს გავაკეთეთ
თქვენთან ერთად ბიჭებს დამთვლელი ერთმანეთს და მეორე შემთხვევაში, როდესაც Jennifer მხოლოდ
ეს გააკეთა აქ, ეს იყო ერთგვარი საქართველოს ფუნდამენტურად უკეთესი.
იმის გამო, რომ ეს არ იყო მხოლოდ ორჯერ სწრაფად.
ეს არ იყო კი ოთხჯერ უფრო სწრაფად.
ეს იყო მთლიანად დამოკიდებული, თუ რა ზომის მითითება, თუ რამდენი
ნაბიჯი, საბოლოოდ მიიღო.
>> ასე რომ, ეს მარტივი იდეა, რომ ჩვენ ყველა აიღო თავისთავად ერთად სატელეფონო წიგნი,
შეიძლება ერთნაირად უნდა იქნას გამოყენებული რაღაც მოსწონს ეს.
და ეს შეიძლება უფრო casually ცნობილია, როგორც თქვენ ალბათ
წარმოიდგინეთ, გათიშე და დაპყრობას.
არ განსხვავებით, რაც ჩვენ გავაკეთეთ, რა თქმა უნდა, ერთად სატელეფონო წიგნი.
>> მაგრამ pseudocode, გაწვევას, სწორედ ეს იყო.
ასე რომ, ჩვენ ამას არ გააკეთებს ეს კიდევ ერთხელ, მაგრამ გავიხსენოთ რომ პირველ კვირას, ჩვენ ყველანი აღუდგა
შემდეგ კი ნახევარი თქვენ დაჯდა, ნახევარი თქვენ დაჯდა, ნახევარი თქვენ დაჯდა.
ეს ალგორითმი განხორციელდა ცოტა მოტყუების გზით, რომ, ის
არ იყო მხოლოდ ერთი me დამთვლელი, ფუნდამენტურად, უფრო ეფექტურად.
ამ შემთხვევაში, მე ოპერაციული ზოგადსაგანმანათლებლო რესურსი.
სახის, მრავალჯერადი პროცესორები, მრავალჯერადი ტვინი, მრავალი ჭკვიანი ადამიანები არიან
ოთახი ეხმარება მე მიიღონ რაღაც წრფივი რაიმე
ლოგარითმული, საწყისი რამე წითელი რაღაც მწვანე.
>> მაგრამ ამ შემთხვევაში, ჯენიფერ მარტო შეუძლია ძირეულად გავაუმჯობესოთ საფუძველზე
შესრულების მისი პირველი ალგორითმის მიერ, ერთხელ, მხოლოდ ფიქრი ცოტა რთული.
ახლა, როდესაც საქმე დროის განხორციელება ეს ყველაფერი, მჭიდროდაა გარეთ
რა ხაზი კოდი შეგიძლიათ დაწერა ასეთი რომ თქვენ შეგიძლიათ ვიმეორებ კიდევ ერთხელ, და
ისევ და ისევ, და ისევ, ერთგვარი ამ looping მოდის.
იმის გამო, რომ თქვენ არ აპირებს ფუფუნება, როგორიც Jennifer გააკეთა, პირველ რიგში, უნდა
უბრალოდ მთელი bunch of სტაბილურობის ინსტრუმენტის და აცხადებენ, hmm, თუ ეს პირველი ნომერი 4,
ნება მომეცით გადასვლა ყველა გზა ბოლომდე.
Ooh, თუ ეს რიცხვი ძალიან დიდია, ნება მომეცით გადაადგილება თვითნებურად უკან
მეორე ელემენტს.
თქვენ იპოვით რომ ეს იქნება ძალიან ბევრი რთული formalize რაც ჩვენ ადამიანები
თავისთავად, როგორც ძალიან გონივრული heuristics, მაგრამ კომპიუტერის მხოლოდ
აპირებს თუ რას ვამბობ, რომ ამის გაკეთება.
>> ახლა ეს ძალიან საინტერესო შედეგები მოჰყვეს.
ეს გრაფაში არის ერთგვარი ნიშნავდა ერთგვარი overwhelm ვიზუალურად, მაგრამ შეამჩნია, სადაც
არის სწორი ხაზი ამ გრაფაში?
სად არის წრფივი გრაფაში რომ ჩვენ მოვუწოდებთ N?
ისე, ეს ერთგვარი მიმართ ბოლოში ამ სურათის, არა?
ამიტომ, ჩვენ გავაკეთეთ არის ჩვენ ერთგვარი zoomed გატარება x-ღერძი და
Y-ღერძი ცდილობენ მისაღებად გრძნობა რა სხვა სახის მოსახვევებში ჰგავს.
>> და სპეციფიკა მათემატიკის გამონათქვამების დღეს არ აქვს მნიშვნელობა, ისე
ბევრი, მაგრამ შეამჩნია, რომ არსებობს ბევრი ალგორითმები, რომ გაცილებით უარესი
რაღაც რომ არის წრფივი.
მართლაც, ო cubed გამოიყურება საკმაოდ ცუდი.
2 ო გამოიყურება საკმაოდ ცუდი. n კვადრატში გამოიყურება საკმაოდ ცუდი.
და ჩვენ ვხედავთ, თუ რა ზოგიერთი ასეთი შესაძლოა, რეალურად დღეს.
და შესვლა n ვერ გრძნობს, როგორც ცუდი, მაგრამ უკეთესია, ვიდრე N არის ჟურნალის ბაზაზე 2 ო.
მაგრამ იცით, ეს იქნებოდა კი უფრო გასაოცარი, თუ Jennifer, ან თუ ჩვენ,
რომ პირველ კვირას, რომ ამუშავება რაღაც რომ არის ჟურნალი ჟურნალის შესახებ n.
>> ასე რომ, სხვა სიტყვებით, არ არსებობს ეს მთელი მრავალი შესაძლებელი გადაწყვეტილებების
პრობლემები, მაგრამ აქაც, განცხადებების რა მოხდება.
როცა დააშორებს, რომელიც ამ მოსახვევებში აპირებს დაამტკიცოს აბსოლუტური
ყველაზე უარესი, ვინც ეკრანზე ახლა?
ასე რომ, ო cubed გამოიყურება საკმაოდ ცუდი მომენტში.
მაგრამ თუ ჩვენ დააშორებს და ვნახოთ მეტი x და y-ღერძი, ვინც აპირებს
დომინირება საბოლოოდ?
ასე რომ, ეს, ფაქტობრივად, გამოდის, რომ 2 ო, და შეგიძლიათ გაერკვნენ ამ out მხოლოდ
ჩართვის ზოგიერთი სულ უფრო და უფრო დიდი ნომრები, და დაინახავთ, რომ 2
ო, რა თქმა უნდა, იღებს უფრო დიდი უფრო სწრაფად.
თუ ჩვენ მართლაც დააშორებს, 2 ო ალგორითმი სრულიად sucks.
ვგულისხმობ ამ აპირებს საკმაოდ ცოტა დრო
კომპიუტერი churn მეშვეობით.
>> მაგრამ დაინახავთ დროთა განმავლობაში, განსაკუთრებით მომავალ პრობლემა კომპლექტი და კიდევ
საბოლოო პროექტები, არის თქვენი მონაცემები კომპლექტი იღებს დიდი, ყველა უფლება?
მაშინაც კი, პირველი ვარიანტი Facebook, როგორც რაოდენობის მეგობრები და
რეგისტრირებულ წევრებს მივიღე დიდი, შეგიძლიათ დასალაგებლად სატელეფონო იგი და
განახორციელოს რაიმე ერთად წრფივი ძებნა, ან ძალიან მარტივია დახარისხება
ალგორითმი, როგორც ჩვენ დავინახავთ დღეს.
თქვენ უნდა დაიწყოს ფიქრი უფრო რთული და უფრო შესახებ ეს პრობლემა.
ხოლო სახის პრობლემები ადგილებში, როგორიცაა Facebook და Google და Microsoft,
და სხვები მუშაობენ, ზუსტად ეს ერთგვარი დიდი მონაცემთა სახის კითხვებით
სულ უფრო და უფრო ამ დღეებში.
>> ყველა უფლება.
ასე რომ, Jennifer წარმატებას, რომ მეორე ალგორითმი, გულწრფელად ვამბობ, მან გააკეთა საოცრად
ასევე პირველად, მაგრამ დაწერა როგორც გისურვებთ, რათა ჩვენ
შეუძლია ამ ეტაპზე.
მეორე შემთხვევაში, იგი leveraged ალგორითმი რომ განმეორდება და
ერთხელ, მაგრამ მან მიანიჭა გარკვეული ვარაუდი, რომ ჩვენ საშუალება მისცა
იგი, მაგრამ იგი ექსპლუატაციაში რამდენიმე დეტალურად მეორედ, რომ მას არ აქვს
პირველად.
რომელიც რა?
>> ეს სია დახარისხებული.
ასე რომ, როგორც კი სია დალაგებულია, ჩვენ აცხადებენ, რომ ჯენიფერი შეძლო ამის გაკეთება
ფუნდამენტურად უკეთესი.
7 კარი, დიახ, არ არის, რომ საინტერესო, მაგრამ ვარაუდობენ, ეს ჩვენ 7 მილიონი კარი.
შესვლა of n ნამდვილად აპირებს შეასრულოს ბევრი, ბევრი
სწრაფად გრძელვადიან პერსპექტივაში.
მაგრამ მას უნდა ჰქონდეს კარი გადანაწილებული მისთვის.
ახლა, მე თავისუფლების აკეთებს, რომ წინასწარ on კომპიუტერის ეკრანზე
აქ, მაგრამ ვარაუდობენ, რომ ჯენიფერი ეს უნდა გააკეთოს, რომ თავად?
ვარაუდობენ, რომ კარი კითხვა წარმოდგენილია მონაცემების მონაცემთა ბაზაში, ან
მეგობრების დარეგისტრირებულ Facebook-ზე, ან ნებისმიერი ვებ გვერდები ინტერნეტში, რომ
სხვადასხვა საიტებზე ალბათ საჭიროა გვერდზე ან ძებნის დასრულდა.
>> დავუშვათ, რომ უბრალოდ ჰქონდა ნედლეული მონაცემები მითითებული და ის დარჩა, რომ თქვენ, ან
Jennifer უნდა გავაკეთოთ, რომ დახარისხება?
ეს, არამედ, მოითხოვს, რომ ჩვენ პასუხის გაცემა კითხვაზე, ასევე, რამდენი დრო
იქნებოდა მიღებული Jennifer, ან თუნდაც ჩემთვის, დასალაგებლად ეს ციფრები წინასწარ ისე
რომ მას შეეძლო ისარგებლოს, რომ?
არა?
იმის გამო, რომ გავლენა, რა თქმა უნდა, თუ ის ჩემთვის სრულიად ხოლო დასალაგებლად
ციფრები, რომელიც heck ზრუნავს, რომ თქვენ შეგიძლიათ ნომრის მსგავსად 50 ისე სწრაფად,
როგორც Jennifer საქმე, თუ ჩვენ უფრო მეტია, ვიდრე overwhelmed თანხა სულ დრო
დასჭირდა by დახარისხება რამ წინასწარ?
>> ასე რომ ვნახოთ, შევძლებთ თუ არა ხატავს სურათს აქ.
მე მაქვს მთელი bunch მეტი სტრესი ბურთები, თუ, რომელიც ეხმარება
დაძვრა აქ.
და თუ თქვენ არ გათვალისწინებით, ჩვენ გვჭირდება შვიდი მოხალისე -
მე, OK.
Wow.
ასე რომ, ჩვენ არ უნდა გაატარონ წლის სამაგიდო ნათურები, როგორც ჩანს.
ყველა უფლება.
ასე რომ, როგორ თქვენს შესახებ ორი წინ.
როგორ შესახებ თქვენ ორი ბიჭები უკან.
ასე რომ ოთხი.
როგორ შესახებ თქვენ წინაშე ხუთი, ექვსი და შვიდი.
უფლება არსებობს.
თქვენი მეგობრის მიუთითებს თქვენ out, ასე რომ თქვენ პრიზი.
>> ყველა უფლება.
კარგით up.
რატომ არ გვაქვს თქვენ ბიჭები მოდის მეტი აქ.
მე ვაპირებ გაძლევთ თითოეული ნომერი.
და წავიდეთ წინ და მოწყობა საკუთარი თავი იდენტურად, თუ რა არის
გამოსახულია ეკრანზე.
>> [INTERPOSING ხმები]
>> დევიდ ჯ Malan: OOP, ბოდიში.
Bug.
ყველა უფლება.
ასევე, აქ მივდივართ.
პუნქტების ხუთ.
პუნქტების ექვსი.
ერთი, ორი, სამი, ოთხი, ხუთი, ექვსი, შვიდი.
ოჰ, ეს უხერხულია.
>> დინამიკები 2: მე უბრალოდ -.
>> დევიდ ჯ Malan: კარგი გარიგება.
ყველა უფლება.
დიდი მადლობა მონაწილეობისათვის.
>> [ტაში]
>> OK.
ყველა უფლება.
ასე რომ, ჩვენ გვაქვს ოთხი, ორი, ექვსი, ერთი, სამი, შვიდი, ხუთი.
Perfect ამიტომ ჩვენ შვიდი მოხალისეები აქ ვინც თანასწორი არიან სიგანე to
მასივი, რომ ჩვენ სათამაშო ადრე.
და მე აირჩია შვიდი მიზეზი რომ იქნება
მოსახერხებელი ცოტა.
და მე ვაპირებ შესთავაზოს პირველია, რომელიც ჩვენ დასალაგებლად ამ შვიდი მოხალისეები.
თუ გსურთ, პირველ რიგში, to მიესალმები თუმცა.
ვინაიდან ეს იქნება უხერხულ რამდენიმე წუთის განმავლობაში.
გააცნოს საკუთარი თავი.
>> GRACE: Hi, მე Grace.
მე ვარ მეორე კურსის შემდეგ Leverett სახლი.
>> BRANSON: Hi.
მე Branson.
მე freshman in WELD.
>> Gabe: Hi.
მე Gabe.
მე უმცროსი in Cabot.
>> ნილ: მე ნილ.
მე freshman in Matthews.
>> JASON: მე ჯეისონ.
მე freshman in Greenough.
>> მაიკ: მე მაიკ.
მე freshman in Grays.
>> Jess: მე Jess.
მე ვარ მეორე კურსის შემდეგ Leverett.
>> დევიდ ჯ Malan: Excellent.
ყველა უფლება.
ისე, მადლობა ყველას, ჩვენი მოხალისეები აქ ჯერჯერობით.
და გამოწვევა ხელთ მიმდინარეობს უნდა იყოს დასალაგებლად ამ ბიჭებს, მაგრამ მერე
ჩვენ ვაპირებთ, უნდა ვიფიქროთ ცოტა მძიმე, თუ როგორ ეფექტურად ჩვენ რეალურად
გადანაწილებული მათ.
მოდით პირველი ცდილობენ ამ.
თქვენ ბიჭები ვხედავთ ერთმანეთის ნომრები უბრალოდ მიერ განთავსების გარშემო კუთხეში.
მე წინ და რამდენიმე წამი, ხოლო დალაგების საკუთარი თავი ეხლა პატარა on
დარჩა უდიდეს მარჯვენა.
წასვლა.
>> OK.
კარგი.
ეს იყო ნამდვილად darn სწრაფად.
ახლა ვინმე აქ, რა იყო ალგორითმი რომ ამ ბიჭებს გამოყენებული?
>> დინამიკები 1: ნაკლებიდან უდიდესი.
>> დევიდ ჯ Malan: OK.
მაინც დიდი მართლაც ერთგვარი ობიექტური, მაგრამ მე არ ვარ დარწმუნებული, რომ ის
მართლაც ალგორითმი.
მაინც დიდი არ გითხრათ მე ნაბიჯ ნაბიჯ რა უნდა გააკეთოს.
ჰო?
>> დინამიკები 1: [inaudible]
>> დევიდ ჯ Malan: OK.
ასე რომ, თუ ხედავთ პირი ნაკლები თქვენი ნომერი, მაშინ გადავა
უფლებას აძლევს.
ასე რომ, ახლა უფრო გამომხატველი, უფრო ალგორითმი, იმიტომ, რომ თქვენ
შეიძლება ითქვას, თუ ეს, მაშინ ეს.
ასე რომ, ჩვენ გვაქვს გარკვეული სახის პირობითი მშენებლობა.
ხოლო ეს ბიჭები, როგორც ჩანს, ამის გაკეთება რამდენიმე ჯერ, რადგან თქვენ გადავიდა ცოტა
საქართველოს მანძილზე.
ასე რომ, სავარაუდოდ რაიმე სახის looping ხდება მათი გონება.
>> მაგრამ მოდით ცდილობენ formalize რომ.
თუ თქვენ ბიჭები შეიძლება აღადგინოთ უკან to ამ შეთანხმებას.
ვნახოთ, შევძლებთ თუ არა formalize ამ ცოტა და შემდეგ ვთხოვთ კითხვას, უბრალოდ
რამდენად ეფექტურია ეს?
რა თქმა უნდა, როდესაც ამას ვაკეთებთ უფრო ნელა, ეს სურვილი რამდენად გრძნობს, როგორც კარგი
ალგორითმი, მაგრამ ვნახოთ, შევძლებთ თუ რომ ჩვენი თითების on ზუსტი ნაბიჯები.
>> ასე რომ ორი ბიჭები არიან ოთხი და ორი.
ან შეგიძლიათ სწორი ან არასწორი ბრძანება?
ცხადია არასწორია.
ასე რომ, ჩვენ swapped.
ახლა მე ვაპირებ გადაადგილება განზე აქ და აცხადებენ, ოთხიდან ექვს.
ხართ თუ არა სწორი ან არასწორი?
>> Gabe: სწორი.
>> დევიდ ჯ Malan: სწორი.
ექვსი და ერთი?
Nope.
გაცვლა.
ასე რომ, ორი გაცვლებს.
ექვსი და სამი?
Nope.
გაცვლა.
ექვსი და შვიდი?
კარგად გამოიყურება.
შვიდი და ხუთი?
>> Jess: [inaudible]
>> დევიდ ჯ Malan: კარგი, მოკლე.
და გადანაწილებული.
ყველა უფლება.
ასე აშკარად არ, არა?
ასე რომ, უფრო გრძელდება.
მაგრამ, რა თქმა უნდა, ამ ბიჭებს, მაშინაც კი, მხოლოდ ინსტინქტურად.
ინახება მოძრაობს.
ისინი არა მხოლოდ შეჩერება, როდესაც მათ შესწორებული ერთი პრობლემა.
ასე რომ.
მართლაც, მე ვაპირებ აქვს იგივეს შვება.
მე ვაპირებ უნდა ერთგვარი გადახვევა უკან დასაწყისში ეს პრობლემა,
ან დასაწყისში მასივი ადამიანი დავიწყოთ მოუწოდებს მათ.
>> ახლა კი რა უნდა ჩემს ალგორითმი მეორე უღელტეხილზე იყოს?
>> დინამიკები 1: იგივე.
>> დევიდ ჯ Malan: იგივე.
ეს კი, მე დაწყებული მინდა, არა?
როგორც კი ნახავთ თავს აკეთებს იგივე ისევ და ისევ, ეს არის ის,
უფრო მოსწონს ალგორითმი, და ნაკლები ადამიანური ინსტიქტი.
>> ასე რომ, ახლა, აქ მივდივართ ისევ.
ორი და ოთხი?
პოსტები
ოთხი და ერთი?
Ah, იყო მართლაც რაღაც მუშაობა ჯერ კიდევ გასაკეთებელი.
და სამი?
კარგი.
ოთხი და ექვსი?
ექვსი და ხუთი?
ექვსი და შვიდი?
კარგი, ახლა, გაკეთდეს.
OK, არ.
მე უნდა დაბრუნდეს.
>> ასე რომ, ახლა, კიდევ ერთხელ, ვაკეთებთ ამ უფრო განზრახ.
ახლა კი, აქ არის მხოლოდ ერთი ტვინის შესრულებაში ეს ალგორითმი.
ერთი CPU, თუ გნებავთ.
და გულწრფელად, რომ ერთადერთი წყარო ჩვენ ვაპირებთ ჰქონდეს.
და კიდევ ჩვენ დაბრუნდეს keyboard და აქვს რაღაც C ჩვენს
განკარგულებაში, ჩვენ მხოლოდ პროგრამის წერა რომ შეუძლია ერთი რამ დროს.
ამასთან, ამ ბიჭებს მომენტში წინ, ჩვენ leveraged მათი ერთობლივი brainpower
ისევე, როგორც ეს ბიჭები გააკეთა კვირაში ნულოვანი.
მოდით შენარჩუნება აკეთებენ.
>> ორი და ერთი.
ორი და სამი.
სამი და ოთხი.
ოთხი და ხუთ.
ხუთი და ექვსი.
ექვსი და შვიდი.
შესრულებულია?
ასე რომ, მე ვარ, მაგრამ ნება მომეცით ითამაშებს ეშმაკის ადვოკატი.
მაქვს, ერთგვარი კომპიუტერი, რომელიც მხოლოდ გააკეთა სწორედ ამ მიმართულებით მასივი
ადამიანი, ვიცი, რომ მე გაკეთდეს?
>> დინამიკები 1: არა
>> დევიდ ჯ Malan: რატომ?
რას უნდა გავაკეთოთ, რათა დავასკვნათ, საბოლოოდ, რომ მე გაკეთდეს?
ალბათ კიდევ ერთი უღელტეხილი.
არა?
იმის გამო, რომ მე ვიცი, რომ წინა უღელტეხილზე არის, რომ მე შესწორებული შეცდომა.
და ეს ნიშნავს, იქნებ არსებობს კიდევ ერთი შეცდომა
რომ მე უნდა გამოსწორდეს.
ასე, რომ შეიძლება იყოს მხოლოდ დარწმუნებული მიერ rewinding და შემდეგ შემოწმების, ერთი ორი, ორი და
სამი, სამი და ოთხი, ოთხი და ხუთი, ხუთი და ექვსი, ექვსი და შვიდი.
OK, ახლა მე არ მუშაობა.
>> მე, რა თქმა უნდა გვახსოვდეს, რომ მე არ მუშაობა რაღაც ცვლადი,
მინდა int.
მას გაცვლებს და თუ სვოპების არის 0 ერთხელ მიიღონ აქ, და ეს დაიწყო 0, მაშინ
მე მხოლოდ სულელური შენარჩუნებას აპირებს წინ და უკან, შემოწმების ერთხელ და
ისევ და ისევ, და ისევ, არა?
იმის გამო, რომ თქვენ გაქვთ დავრჩებოდით ზოგიერთი სახის უსასრულო ციკლი.
ასე რომ, როგორც კი იქ 0 გაცვლებს, ცალსახად შეიძლება ითქვას, რომ ეს
ალგორითმის მართლაც სრული.
>> ახლა მოდით დააყენა სახელი ამ.
ალგორითმი, რომელიც მე ვთავაზობ ჩვენ უბრალოდ განხორციელებული არის რაღაც მოუწოდა bubble
დალაგების, ცნობილია, როგორც ასეთი იმ თვალსაზრისით, რომ ციფრები, რომლებიც უფრო დიდ სახის
bubble მათი გზა მდე საუკეთესო, ან ბოლომდე მასივი ნომრები.
მაგრამ რამდენად ეფექტურია იყო ეს ალგორითმი?
რამდენი ნაბიჯები არც მე ფიზიკურად უნდა მიიღოს, მაგალითად, დასალაგებლად ამ
შვიდი ადამიანები?
>> ოთხი ხუთი?
OK, ძალიან ბევრი საბოლოოდ იქნება პასუხი.
მაგრამ მაშინაც, კონკრეტული რაოდენობა ასე არ არის საინტერესო.
მოდით განზოგადება მას, როგორც ო.
ასე რომ, თუ მე n ხალხს აქ, და ისინი იყო, ერთგვარი, შემთხვევითი წესრიგის
დასაწყისში, რომ ორიგინალური მიზნით.
ისე, რამდენი ნაბიჯები არც მე მაქვს მიიღოს პირველ უღელტეხილზე?
ეს იყო ერთი, ორი, სამი, ოთხი, ხუთი, ექვსი და ისინი შვიდი ადამიანი, ასე
ეს არის ის, შვიდი, ექვსი - ისე, რომ ის ო მინუს ერთი ნაბიჯი პირველად.
>> ახლა, რამდენი ნაბიჯები არც მე მაქვს მიიღოს როდესაც მე rewound?
ასევე, ჩვენ შეიძლება რეალურად გაორმაგდება, რომ თუ ჩვენ ნამდვილად უნდოდა, მაგრამ ახლა, მე ვარ
უბრალოდ თქმას, ყველა უფლება, კიდევ ერთი N მინუს 1.
ასე რომ, ო მინუს 1 აპირებს მიიღოს შემაშფოთებელი შენარჩუნება სიმღერა, მოდით
უბრალოდ გარშემო up ოდნავ.
ასე რომ 2n ნაბიჯები.
ასე რომ, 14 ნაბიჯები, მისცეს ან.
>> რამდენჯერ მე ნაბიჯი მომავალი დრო?
ისე, ეს 3N.
ნამდვილად.
ახლა კი, უარეს შემთხვევაში, მაგალითად, რამდენი უნდა ჰქონდეს
წავიდა და უკან, წინ და უკან, შესრულებაში ეს ალგორითმი, შევცვალე
ადამიანი ყოველ უღელტეხილზე, უხეშად?
ეს, ფაქტობრივად, n კვადრატში, არა?
>> იმის გამო, რომ უარეს შემთხვევაში, შეგიძლიათ სახის საქართველოს ფიქრობთ ამ ინტუიციურად,
მიუხედავად იმისა, რომ შესაძლოა პატარა ცოტა დრო ჩაძირვაში სისტემაში
უარეს შემთხვევაში, რა ეს შვიდი ადამიანი ჩანდა, in
თვალსაზრისით მოწყობა მათი ნომრები?
სრულიად უკან, არა?
და მხოლოდ სიმულაცია რომ, რა იყო თქვენი სახელი ერთხელ?
>> მაიკ: მაიკ.
>> დევიდ ჯ Malan: მაიკ?
კარგი, მაიკ, შეიძლება უბრალოდ შეუერთდეს me მეტი აქ მხოლოდ ერთი მეორე?
ფაქტობრივად, არ.
ბოდიში მაიკ, მოდით გადახვევა.
რა არის შენი სახელი ისევ?
>> ნილ: ნილ.
>> დევიდ ჯ Malan: ნილ.
OK, ნილ, თქვენ მოდის ჩემთვის, თუ არ იბადება.
ამიტომ, მე ვაპირებ შესთავაზოს, მხოლოდ სიმარტივის, რომ ნილ არის მისი
ყველაზე უარესი შემთხვევაში.
მაგრამ გავიხსენოთ, როგორ განხორციელდება ჩემი ალგორითმი.
მე შედარებით შედარებით შედარებით, შედარებით შედარებით, რა.
ახლა ეს ბიჭები არიან out მწყობრიდან, ამიტომ დაფიქსირება.
ასე, რომ თქვენ ბიჭები მოკლე.
თუმცა მიიჩნევს, ახლა, თუ რამდენად შორს ამჯამად ნილ უნდა წავიდეს?
ეს დაახლოებით N.
თქვენ იცით, რომ ეს არ არის რეალურად N.
ეს იგივეა, N მინუს 1, მაგრამ მე მისაღებად გააღიზიანა შენახვა კვალს პატარა
ნომერი, მოდით უბრალოდ ეძახით N.
>> ასე რომ, თუ ნილ მოძრაობს ერთი ნაბიჯია მაქსიმალურად ყოველ დრო და გადაადგილება ნილ ერთი ნაბიჯია,
უნდა მოხდეს ეს მართლაც tedious უღელტეხილზე უკან და მეოთხე, ეს არის უხეშად
ამით, ო ნაბიჯები, სულ ო ჯერ, იმიტომ, რომ ეს აპირებს მიიღოს me
რომ ბევრი ნაბიჯები მისაღებად ნილ ყველა გზა, სადაც მას ეკუთვნის.
დავანებოთ ყველას, თუ ბიჭები ყველანი mis-უბრძანა ასევე.
>> მოდით მოვუწოდებთ bubble sort n კვადრატში.
ქრონომეტრაჟი ამ ალგორითმი, შესრულების ეს ალგორითმი,
ეფექტიანობის ამ ალგორითმი, ჩვენ უნდა უბრალოდ აღწერს მეტი
ზოგადად, როგორც n კვადრატში.
რა კარგია, იმიტომ, რომ მე ვერ გააკეთებდა იგივე მაგალითი რვა ადამიანი, ცხრა
ადამიანი, მილიონი ადამიანი, და რომ პასუხი არ შეიცვლება.
>> ასე რომ, თუ თქვენ ბიჭები არ იბადება, მოდით გადატვირთვის თქვენ სადაც თქვენ დაიწყო.
და მოდით ვცდილობთ ორი სხვა მიდგომები და თუ ვერ ვახერხებთ, ფუნდამენტურად
უკეთესი, ვიდრე ეს.
ასე რომ, ამ დროს, მე ვაპირებ შესთავაზოს დალაგების სხვადასხვა ალგორითმი.
ეს იყო ძალიან ჭკვიანი ჩვენგანი ბოლო დროს, და თქვენ ბიჭები იყვნენ უფლება აქვს
მარჯვენა ინსტინქტები მხოლოდ სახის საქართველოს შევცვალე pairwise.
მაგრამ თუ ნამდვილად სურდა მივუდგეთ ამ უბრალოდ, ჩემი მიზანია, რომ გადაადგილება
ყველა პატარა ნომრები ამ გზით, და დააყენებს ყველა დიდი ციფრები, რომ
გზა, რატომ არ მე უბრალოდ, რომ ყველაზე გულუბრყვილო გზა შესაძლებელი და თუ მე
შეუძლია გააკეთოს უკეთესი, ვიდრე რა იყო საკმაოდ კომპლექსური ალგორითმი?
>> ასე რომ, ვნახოთ.
ოთხი არის საკმაოდ მცირე რაოდენობა, ასე რომ მე დატოვებს თქვენ იქ მომენტში.
Ooh, ნომერი ორი არის უფრო უკეთესი.
ასე რომ, შეგიძლიათ უბრალოდ წინ გადადგმული ნაბიჯია ერთი წუთით?
ეს არის გაკეთებული ჩემს პატარა დანომრილი კანდიდატი, და მე ვაპირებ უნდა გვახსოვდეს
რომ, მინდა, განსხვავებულია.
მაგრამ მე ვაპირებ შენარჩუნება შემოწმების.
არსებობს თუ ვინმე რომლის ნომერი მცირეა?
ექვსი, არ.
Oh, იქ ნილ ერთხელ.
>> ამიტომ, მე ვაპირებ დააყენებს თქვენი დაბრუნება ერთგვარი კონცეპტუალური.
ნილ მოვა ნაბიჯია.
ახლა კი, ცვლადი, რომ მე იყენებს შენარჩუნება სიმღერა, რომელსაც აქვს პატარა
ნომერი განახლებული შეიცავს ნილ ადგილსამყოფელი.
ისე, ვნახოთ.
სამი, შვიდი, ხუთი.
კარგი, მე ვიცი, ნილ იყო პატარა.
რა არის მარტივი რამ ჩემთვის ქნას?
მე არ ვაპირებ დაგვრჩა ჩემი დრო მხოლოდ bubbling ნილ ერთ ადგილზე წავიდა.
რატომ არ მე უბრალოდ დააყენა ნილ სადაც იგი ეკუთვნის, რაც, რა თქმა, სადაც?
>> ყველა გზა დასაწყისში.
ასე რომ, ნილ, მოდის ჩემთან ერთად.
და რა იყო თქვენი სახელი ერთხელ?
>> მადლი: Grace.
>> დევიდ ჯ Malan: Grace.
OK.
ასე რომ უნეტარესის, სამწუხაროდ, თქვენ სახის გზა.
ასე რომ, როგორ უნდა მოაგვაროს ეს პრობლემა?
არა?
თუ ეს მასივი, იქ მხოლოდ შვიდი ადგილებში.
შეგახსენებთ, რომ, ძარცვა, ჩვენ ვისაუბრეთ გამოცხადების ასაკის, და ჩვენ მხოლოდ
სასრულ რაოდენობას ასაკის?
იგივე იდეა აქ.
ჩვენ მხოლოდ სასრული რაოდენობის ints.
მადლი არის ერთგვარი ჩვენს სხვათა შორის, ასე როგორ უნდა დააფიქსიროს?
>> მარტივი ჰგავს, უნეტარესის, ვწუხვარ.
თქვენ აპირებს უნდა წავიდეს მეტი იქ ასე შეიძლება გავაკეთოთ ოთახი.
ახლა კი, თუ ფიქრობთ ამ, შესაძლოა, ჩვენ მხოლოდ გააკეთა პრობლემა გაუარესდა.
და, შესაძლოა, ჩვენ გავაკეთეთ, რადგან რა, Grace იყო სწორი ადგილი?
მაგრამ ჩვენ ვიცით, რომ ის არ არის, რადგან წინააღმდეგ შემთხვევაში, იგი იქნებოდა
იდგა ნაბიჯია ნაცვლად ნილ ამ დროს, არა?
ჩვენ უკვე შეამოწმეს მისი ნომერი გამოვიდა.
>> ყველა უფლება.
ასე რომ, ახლა, ნილ არის სწორი ადგილი, და შემიძლია მცირე ოპტიმიზაცია.
მომდევნო წუთი, მე ვაპირებ იგნორირება ნილ ყველა ერთად, ისე, რომ არ
დაგვრჩა თავის დროზე ან შემთხვევით სვოპ მას არასწორ ადგილზე.
ასე რომ, ახლა, როგორ უნდა მოვძებნოთ შემდეგი ელემენტი, რომელიც ყველაზე პატარა?
ორი.
ეს არის ის, საკმაოდ კარგი ნომერი, თუ გსურთ წინგადადგმული ნაბიჯი და
მე მახსოვს, თქვენ.
ექვსი, არ არის კარგი.
ოთხი, სამი, შვიდი, ხუთი, არ არის კარგი.
ნება მომეცით, გადაადგილება თქვენ თქვენი სწორი ადგილი.
და ჩვენ მხოლოდ მიიღო იღბლიანი ამ დროს.
>> ახლა, მე ვაპირებ იგნორირება ამ ორი ბიჭებს, ახლა ამის გაკეთება კიდევ ერთი
სწორედ ამ მიმართულებით.
ექვსი, რომ საკმაოდ მცირე რაოდენობით.
კარგით წინ.
ო, ბოდიში.
Grace ნომერი უკეთესია, ასე ნაბიჯი წინ.
ოთხი.
ვწუხვარ, Grace.
დაბრუნება კიდევ ერთხელ.
პუნქტების სამი უკეთესია.
შვიდი.
ხუთი.
ახლა კი რა არის თქვენი სახელი ერთხელ?
>> JASON: ჯეისონ.
>> დევიდ ჯ Malan: ჯეისონ.
ასე რომ, ჯეისონ არის პატარა ელემენტს მე შერჩევა.
სად არის იგი აპირებს წავიდეს?
ასე რომ, სად ექვსი არის.
და შენი სახელი ისევ?
>> Gabe: Gabe.
>> დევიდ ჯ Malan: Gabe.
Gabe ის გზა.
რა არის ყველაზე იოლი საქმეა?
გაცვლა ამ ორ ბიჭებს და გაგრძელდება.
ასე რომ, ახლა ვნახოთ.
ვინ არის ყველაზე პატარა?
ოთხი.
ნება მომეცით მხოლოდ სახის მოტყუებას.
ხუთი იქნება პატარა.
მე მომდევნო, თუ, გსურთ დახევას წინ, რა უნდა გავაკეთოთ
ეს ბიჭები, ერთად Gabe?
გაცვლა კიდევ ერთხელ.
ახლა, მაინც ოდნავ მწყობრიდან.
აღმოვაჩინე Gabe უნდა იყოს პატარა, ასე მე პოპ მას, გადაადგილება თქვენ ბიჭები დასრულდა.
და გაკეთდეს.
>> ასე რომ, პასუხი არის იგივე.
საბოლოო ჯამში არის იგივე.
რომელი ამ ორი ალგორითმები უკეთესია?
მეორე, მე გავიგე.
რატომ?
>> დინამიკები 3: ეს n ნაბიჯები [inaudible].
>> დევიდ ჯ Malan: ეს ო ნაბიჯები უმეტეს.
საინტერესო.
ისე არა?
ასე რომ, რა მე პატარა ელემენტს?
რამდენი ნაბიჯები არც მე უნდა მიიღოს იპოვოს ყველაზე პატარა ელემენტს?
მე გამოიყურება ყველა გზა დასასრულს, არა?
იმის გამო, რომ უარეს შემთხვევაში, რა თუ ნილ იყო აქ?
ასე რომ მხოლოდ მოძიებაში ყველაზე პატარა ელემენტს იღებს me n ნაბიჯები, ან ო მინუს 1.
თუმცა, OK.
ასე დაფიქსირება ნილ.
გახსოვდეთ, რომ, ერთი წუთით, არც ისე წინ.
>> მაგრამ რა მე მომავალი პატარა ელემენტს?
ეს ო მინუს 1, ან ო მინუს 2 ნამდვილად, ეხლა ისეთი ნაბიჯი.
ასე რომ, OK.
ასე რომ, მე n მინუს 2.
ყველა უფლება.
ასე რომ გრძნობს ცოტა უკეთესი.
ყველა უფლება.
რამდენი ნაბიჯები მომავალი დრო მოძიების ნომერი სამი?
ასე რომ, ო მინუს 4.
ამიტომ მცირდება, ერთი ნაკლები ნაბიჯი ყოველ iteration.
ასე რომ, ეს იმას თავს კარგად გრძნობენ, არა?
თუ ბოლო პერიოდში კი დაახლოებით n ჯერ n, ამ დროს ეს ო მინუს 1, პლუს ო minus
2, პლუს ო მინუს 3, პლუს ო მინუს 4, dot, dot, dot.
მაგრამ თუ გავიხსენებთ თქვენი უმაღლესი სკოლის სახელმძღვანელოების, პატარა მოტყუებას
ფურცელი უკან რომ აქვს ფორმულები, თუ თქვენ დაამატოთ ეს სერია ნომრები,
რა არის საერთო რაოდენობის ნაბიჯები იქნება, რომ მე აქ?
>> ეს არის ერთ ერთი იმ, მინდა, ო minus 1, ჯერ n, იყოფა 2.
ნება მომეცით, თუ მე შეიძლება გაიყვანოს ეს ყველაფერი მხოლოდ ერთი წუთით.
ისევ და ისევ, მე ვარ ასეთი დამრგვალება ზოგიერთი ციფრები, მხოლოდ იმისათვის, რომ შევინარჩუნოთ ცხოვრების უბრალო,
მაგრამ, როგორც მახსოვს, ეს რაღაც, თუ გავაკეთო ო მინუს 1 რამ, მაშინ n minus
2, შემდეგ n მინუს 3, ეს უხეშად მსგავსი რამ დაახლოებით 2, და თუ
გამრავლების ამ out, სწორედ რეალურად ო მოედანზე.
ამით არ შეგრძნება ძალიან კარგი. ო მინუსი n მეტი 2.
>> მაგრამ აქ რამ.
კომპიუტერული მეცნიერების, როდესაც პრობლემები დავიწყოთ საინტერესო არის, როდესაც n
იღებს მართლაც დიდი.
ხოლო როდესაც n იღებს მართლაც დიდი, რომელი ეს ფასეულობები აპირებს დომინირებს ყველა
საქართველოს სხვები?
ეს არის სახის n კვადრატში, არა?
დიახ, გამყოფი 2 არის საკმაოდ კარგი.
მაგრამ თუ ვსაუბრობთ მილიარდობით ცალი მონაცემების, ან ტრილიონობით
ცალი მონაცემებით, კი ბატონო, ასე თქვენ ორჯერ სწრაფად.
მაგრამ, ვინც ნამდვილად ზრუნავს თუ ეს დიდი რაოდენობით, თუ არა ეს ფაქტორი არის ის, რაც იღებს
უფრო დიდი და უფრო დიდი.
და რა თქმა უნდა, ეს ქმნის მეტი სხვაობა, ვიდრე ეს ბიჭი.
ასე რომ, მიუხედავად იმისა, რომ თქვენ ბიჭები არიან უფლებას, მეორე ალგორითმი, ჩვენ მას
შერჩევის დალაგების, არის, რეალურ ცხოვრებაში, ცოტა სწრაფად პოტენციურად, რადგან მე ვარ
მიღების ნაკლები და ნაკლები ნაბიჯებს ყოველ ჯერზე.
>> ეს არ არის ნამდვილად საფუძვლიანად სწრაფად.
იმიტომ, რომ თუ ჩვენ რეალურად შეუძლია ამ გარეთ დიდი ღირებულებები N, წლის ბოლოს
დღეს, დიდი საკმარისი n, ეს ჯერ კიდევ მიმდინარეობს თავს საკმაოდ ნელი.
ასევე, ნება მომეცით მიიღოს ერთი ბოლო უღელტეხილზე იმ.
ეს არის ის რაც მინდა მოვუწოდო შერჩევა ერთგვარი.
შეგიძლიათ ბიჭები აღადგინოთ საკუთარი თავი ერთი ბოლო დროს?
ხოლო ამ უკანასკნელ შემთხვევაში, მე ვაპირებ შესთავაზოს რაღაც
მოუწოდა ჩანართი ჯიშია.
Insertion დალაგების მიმდინარეობს, კონცეპტუალურად, ოდნავ განსხვავებული.
>> იმის ნაცვლად, რომ ბრუნდება და მეოთხე და შერჩევის ყველაზე პატარა ელემენტის, მე ვარ
უბრალოდ აპირებს გამკლავება თითოეული ამ ბიჭები, როგორც მე ექმნებათ მათ, და ჩადეთ
თავიანთ სწორი ადგილი.
ასე რომ, მე მხოლოდ აპირებს დაიწყოს უნეტარესის, და მე ვხედავ, რომ ის ნომერი ოთხი.
სად ნომერი ოთხი ეკუთვნის?
მე არ დახარისხება დაიწყო არაფერი, ასე Grace იღებს დარჩენა უფლება არსებობს.
ახლა კი მე ვაპირებ აცხადებენ, თუ შეიძლება მიიღოს ნაბიჯი თქვენი უფლება, ამ
ჩემი დახარისხებული სია, ეს არის ჩემი დაუხარისხებელი დარჩენილი სიაში.
ასე რომ, ახლა მე ვაპირებ გაგრძელება მომდევნო, და თქვენი სახელით კიდევ ერთხელ?
>> BRANSON: Branson.
>> დევიდ ჯ Malan: Branson.
ასე რომ, Branson არის ნომერი ორი.
ამიტომ, მე ვაპირებ თქვენ გარეთ მომენტში.
ახლა, სად ეკუთვნის ამ მასივი?
ასე რომ, უფლება მადლი.
ასე რომ, კიდევ ერთხელ, ჩვენ სახის მიღების Grace ბევრი სამუშაო აქ.
სად დააყენა თქვენ?
ასე რომ, ჩვენ ვაპირებთ ლღობას თქვენ დატოვა და ჩადეთ Branson არსებობს.
მაგრამ ახლა მე აცხადებენ, რომ თქვენ ბიჭები კეთდება.
მაგრამ შეამჩნია, მე არ იყენებს დამატებითი სივრცე.
ეს ჯერ კიდევ 2 ელემენტები აქ, 5 მეტი აქ.
სულ მასივი ზომა არის 7, ამიტომ მე არ მოტყუების, ყველა უფლება?
>> ასე რომ, ახლა ჩვენ გვაქვს, ერთად Gabe აქ, ნომერი ექვსი, სად ეკუთვნის?
თქვენ მიიღო იღბლიანი ერთხელ.
ასე რომ თქვენ დარჩენას უფლება არსებობს.
უბრალოდ მცირე ნაბიჯი სწორი მხოლოდ იმისათვის, რომ ნათელია, რომ თქვენ გადანაწილებული.
ახლა ჩვენ გვყავს ნილ ერთხელ, ნომერი ერთი, სად წავიდეთ?
ახლა კი არის, სადაც ჩვენ დავიწყოთ, რომ ეს ალგორითმი, თუმცა პირველი
ერთი შეხედვით, გრძნობს საკმაოდ ჭკვიანი, უყურებს რა არის დაახლოებით მოხდეს.
თუ თქვენ წინ გადადგმული ნაბიჯია.
>> სად გვინდა, რომ დააყენა ნილ?
ასე რომ, ცხადია, აქ, ისე, თუ როგორ ნუ მივიღებთ ნილ იქ?
მოდით ეს ნაბიჯ ნაბიჯ.
Gabe, სად უნდა წავიდეთ?
Yep, ასე მიიღოს ერთი დიდი ნაბიჯი, ან ორი ნახევარი ნაბიჯები, რათა
ერთი ნაბიჯია იქ.
უნეტარესის, თუ სად წავიდეთ?
კარგი.
ასე რომ, კიდევ ერთ ნაბიჯს.
და ბოლოს, Branson?
კიდევ ერთი ნაბიჯი.
ახლა კი ჩვენ შეგვიძლია დააყენა ნილ შევიდა ადგილი.
>> ასე რომ, ახლა, გააგრძელოს ამ ლოგიკით.
მიუხედავად იმისა, რომ ჩვენ არ გადავიდა ნილ მეტი და მეტი და მეტი, იმისათვის, რომ მას
სადაც ის მიდის, უარეს შემთხვევაში, მომდევნო ნომერი შეიძლება ექმნებათ იქნებოდა
იყოს რიცხვი, ვთქვათ, იყო რიგი ნულოვანი, მაშინ ჩვენ ვაპირებთ გადაიტანოს ყველა
ამ ბიჭებს.
დავუშვათ, რომ არსებობს მთელი რიგი, უარყოფითი ერთი,, ჩვენ უნდა გადაიტანოს
ყველა ამ ბიჭებს.
ასე რომ, ჩვენ რეალურად მხოლოდ სახის flipping პრობლემის გარშემო, როგორიცაა, რომ ჩვენ
გადაცემის ხარჯზე დან შერჩევის პროცესი ასე ჩასაგდები
პროცესი, ისეთი, რომ თქვენ ბიჭები მქონდა გადაადგილება დაახლოებით N მინუსი რაღაც
რიგი ნაბიჯები.
და ეს ისეთი ნაბიჯი, რომელიც მხოლოდ აპირებს რომ გაიზარდოს როგორც მე მოვნიშნოთ ნომრები,
თუ მე უნდა შევინარჩუნოთ shoving თქვენ ბიჭები უკან, და უკან, და უკან.
>> ასე რომ სამწუხარო ის, ყველა ეს ალგორითმები არიან n კვადრატში.
მოდით წავიდეთ წინ და მადლობა ამ ბიჭები და ვიზუალურად ეს ცოტა
განსხვავებულად.
ძალიან კარგად გაკეთდეს.
>> [ტაში]
>> ყველა უფლება.
აქ თქვენ წასვლა.
მადლობა -
>> BRANSON: [inaudible] შენარჩუნება ნომრები.
>> დევიდ ჯ Malan: არა, შეგიძლიათ შენარჩუნება ნომრები, ასევე.
ყველა უფლება.
ლამაზად კეთდება.
ყველა უფლება.
მოდით ვნახოთ, შევძლებთ თუ არა ახლა შეაჯამებს უფრო სწრაფად და უფრო ვიზუალურად,
ზუსტად ის, რაც მხოლოდ მოხდა აქ ასეთია.
მე ვაპირებ წავიდეთ წინ და გაიყვანოს up Firefox.
ჩვენ ამას უკავშირებენ აქცია მე რა თქმა უნდა ნახვა.
ჯავის ოდნავ შემაშფოთებელი მისაღებად სამუშაო ზოგიერთ ბრაუზერები ამ დღეებში.
ასე რომ, თუ თქვენ ჩვენგან თამაში ამ სახლში, გააცნობიეროს, თქვენ უნდა გამოვიყენოთ Firefox
მიიღოს ეს მუშაობა.
და რა მე ვაპირებ ვუყოთ აქციის შემდეგ.
>> ბოლოში, მე მაქვს მთელი bunch of მენიუს ვარიანტი, მათ შორის დაწყება და
შეწყვიტოს ღილაკს.
გარდა ამისა, როგორც განზე როგორც ჩანს, bug ამ პროგრამებში, სადაც თქვენ
ვერ რეალურად ვხედავ დაწყების ან შეწყვიტოს ღილაკს, სანამ არ გამართავს სარდლობის ან Alt
პლუს და მასშტაბის, რომელიც საინტერესოა გამოიტანს უფრო ღილაკებით.
ასე რომ მხოლოდ FYI თუ ითამაშებს ამ სახლში.
ახლა მე ვაპირებ დააწკაპუნეთ დაწყება მხოლოდ მომენტი, შემდეგ მიუთითებს შეფერხებას,
ისევე როგორც, 200 მილიწამში აქ, უბრალოდ ასე რომ, ჩვენ ვხედავთ, რა მოხდება.
>> ასე რომ, ამტკიცებენ, რომ ეს არის ვიზუალიზაციის პირველი ალგორითმი
ეს ბიჭები გააკეთა, bubble sort, რომლის ჩვენ swapped ადამიანი წყვილი-ბრძენი.
გასაღები რისთვისაც, ამ ვიზუალიზაცია ის არის, რომ სიმაღლე ბარები
წარმოადგენს ზომის ნომერი.
ასე რომ, taller ბარი, უფრო დიდი რაოდენობის.
მოკლე ბარი, პატარა ნომერი.
და თუ შეამჩნია, ჩვენ ვაპირებთ მეშვეობით პირველი iteration ამ ალგორითმი,
შევცვალე დიდი და მცირე რაოდენობით, ისე, რომ მცირე რაოდენობა მოდის პირველი და
დიდი რაოდენობით ღებულობენ უფლება.
>> და როგორც კი მივიღებთ ბოლოს მასივი ბევრი უფრო ნომრები ათზე, ჩვენ
აპირებს დაბრუნდეს დასაწყისში.
და ითვალისწინებდეს ამ.
მარცხენა მოშორებულ, რომ პატარა ბიჭი აპირებს სვოპ მხარეს, და ეს
პროცესი მეორდება.
ახლა ეს ვიზუალიზაცია სწრაფად იღებს მოსაწყენი, ასე რომ, ნება მომეცით წავიდეთ წინ და შეწყვიტოს
იგი, შეცვალოს დაგვიანებით რაღაც ბევრად სწრაფად მხოლოდ მისაღებად, ახლა ფიქრობს
ეს ალგორითმი.
>> ასე რომ, მიუხედავად იმისა, რომ მე თავისი გუნდი ის, რომ ეს არის მოსწონს ამაღლების ჩემი პროცესორი, ყიდულობს
ახალი კომპიუტერი.
მე არ ძირეულად შეცვალა ჩემი ალგორითმი, მაგრამ თქვენ შეიძლება მართლაც უფრო მეტი
ნათლად, ვიდრე ადამიანი, რომელიც დიდი ციფრები bubbling მდე საუკეთესო,
და პატარა ციფრები bubbling ქვემოთ ბოლოში.
ახლა კი ეს საგანი აქ ინახება.
და როგორც გარდა, ამ მოედნებზე, არ არსებობს რამოდენიმე აღრიცხვის იქ
დაგეხმაროთ ითვლიან რამდენი შედარება, ან რამდენი სვოპების აქვს
რეალურად გაკეთდა.
>> ასევე, შევეცადოთ ერთი სხვები დავინახეთ.
ნება მომეცით დააწკაპუნეთ bubble sort აქ, და ნება მომეცით აირჩიოს და ეს მთელი ვებ გვერდზე
ცოტა buggy.
მოდით მიიღოს რისკი და აწარმოებს კიდევ ერთხელ.
იქ ჩვენ წავიდეთ.
მოდით გავაკეთოთ შერჩევა ერთგვარი.
არ ვიცი, რატომ მენიუ როგორც ჩანს, იქ.
მოდით მასშტაბირების დაფიქსირება, რომ შეცდომაა, შეცვლის 50.
Ah, მოდით რეალურად გააკეთებს რომ უფრო სწრაფად.
ხუთი მილიწამებში ან ასე იქნება, და დაწყება.
>> ასე რომ, ეს შერჩევის სახის.
ასე რომ, კიდევ ერთხელ, ვიფიქროთ, რაც ჩვენ გააკეთა ადამიანები აქ.
ჩვენ გამოვიარეთ მასივი შეარჩია ყველაზე პატარა ელემენტი, კიდევ ერთხელ,
და ისევ, და ისევ.
ახლა კი აცხადებენ, რომ ჯერ კიდევ ძალიან ცუდი.
ეს იყო ჯერ კიდევ n კვადრატში, მისცეს ან, მაგრამ ეს იყო, რეალურ სამყაროში, ცოტა
სწრაფად, იმიტომ, რომ მე ნამდვილად აღების ოდნავ ნაკლები ნაბიჯები ყოველ ჯერზე.
მაგრამ ჩვენ მხოლოდ ვსაუბრობთ, თუ რა?
შესაძლოა 40 ან იმდენად ბარები აქ?
ჩვენ არ ვსაუბრობთ 40 მლნ.
ამიტომ არ არის სრულიად ნათელი, რომ მართლაც მნიშვნელოვანი მომატება.
>> ნება მიბოძეთ ახლა დაბრუნდეს და შეცვალოს ჩვენი მესამე ალგორითმი, რომელიც შერჩევა
ჩანართი ჯიშია.
ახლა კი ეს ნამდვილად buggy რადგან menu ნამდვილად არ უნდა იყოს დახვდა.
ასე რომ, ახლა ჩვენ გადახვევა უკან აქ და დავიწყოთ ეს ალგორითმი.
Whoop, დაწყებისა და გაჩერების.
ასე რომ, ეს ერთი სახის აქვს საკმაოდ ნიმუში მას, რომლის დროსაც ჩვენ კვლავ
ჩასმის ადამიანი, ან ამ შემთხვევაში, ბარები შევიდა
შესაბამის ადგილას.
და ეს უკვე გააკეთა ადრე მე აღმოჩნდა გარშემო.
მაგრამ ეს ერთი, ძალიან, თეორიულად, ჯერ კიდევ n კვადრატში.
>> ასე რომ ვნახოთ, შევძლებთ თუ არა შეაჯამებს ეს შემდეგნაირად.
მე ვაპირებ წავიდეთ წინ და უბრალოდ მისცეს ჩვენს ერთგვარი საერთო გზა ვსაუბრობთ
აღნიშნულ საკითხებთან ერთად, ნება მომეცით წარმოგიდგინოთ უბრალოდ ცოტა notation აქ.
თქვენ შესახებ, რომ ნახოთ რაღაც მოუწოდა დიდი ო, იმიტომ, რომ ეს ფაქტიურად დიდი
ო და ეს არის გზა, რომელიც კომპიუტერული მეცნიერს ან მათემატიკოსი კი იყენებს
აღწერა ქრონომეტრაჟი ზოგიერთი ალგორითმი.
რამდენი ნაბიჯები სჭირდება პრაქტიკულად?
>> ახლა მე ვაპირებ გართულებების თავს ერთად ჩემი ხელწერა აქ რაღაც მომენტში.
მაგრამ ნება მიბოძეთ წავიდეთ წინ და ამბობენ, რომ ეს იქნება დიდი O მეტი აქ.
და ნება მომეცით წარმოგიდგინოთ ერთი სხვა სიმბოლო, დედაქალაქში omega.
Omega იქნება, პირიქით, არსებითად, დიდი ო ვინაიდან დიდი O
საშუალებებით, უარეს შემთხვევაში, რამდენ დროს შესაძლოა, ზოგიერთი ალგორითმი მიიღოს, ამ
თვალსაზრისით N, omega აპირებს იყოს რამდენ დროს შეიძლება იგი
მიიღოს საუკეთესო შემთხვევაში.
და ჩვენ ვხედავთ, რას ვგულისხმობთ საუკეთესო შემთხვევაში რაღაც მომენტში.
>> მოდით ახლა გადავიდეთ რაღაც მარტივი.
ნება მომეცით იწყება წრფივი ძიება.
ასე რომ, არა დახარისხება.
ჩვენ ამას დავარქმევთ წრფივი ძიება.
ახლა კი, მიიღოს პატარა მაგიდა აქედან.
ახლა კი, იმ შემთხვევაში, წრფივი ძებნა, უარეს შემთხვევაში, რამდენი ნაბიჯების გადადგმას
იგი აპირებს me იპოვონ რიგი თვითნებური არჩევანი?
და არ არსებობს N სულ კარი ან N სულ ნომრები.
უარეს შემთხვევაში.
რამდენი ნაბიჯები ვარ მე აპირებს უნდა მიიღოს მოძიების ნომერი 50 მასივში
საქართველოს ო კარი?
და რატომ?
იმის გამო, რომ ეს შეიძლება იყოს ყველა გზა მეტი გადატანა ბოლომდე.
ასე რომ ჰგავს Jennifer შეექმნა, ნომერი 50 იყო ყველა გზა დასრულდა, ისე
უარეს შემთხვევაში წრფივი ძებნა დიდი ო ნ, ჩვენ ვთქვა.
>> რაც შეეხება საუკეთესო შემთხვევაში, თუ თქვენ ნამდვილად გაუმართლა?
უბრალოდ აპირებს ერთი ნაბიჯია, ან მუდმივი რიგი ნაბიჯები.
ასე რომ, ჩვენ აღწერს, რომ როგორც 1.
ასე რომ, ეს არის საკმაოდ კარგი.
ახლა რა მოხდება, თუ ჩვენ გავაკეთეთ რაღაც მინდა ორობითი ძიება?
ასე რომ ბინარული ძებნის, უარეს შემთხვევაში, აიღო რა დრო?
>> [INTERPOSING ხმები]
>> დევიდ ჯ Malan: ასე რომ, რეალურად, მე ესმა რამდენიმე ადგილებში.
ასე რომ, ეს, ფაქტობრივად, სისტემიდან N, მისცეს ან, რადგან როგორც ჩვენ დაყოს სია ნახევარ
ისევ და ისევ, და ისევ, და ისევ, ჩვენ საშუალება მოძიების, საბოლოო ჯამში, ღირებულება,
თუ ეს არსებობს, მაგრამ არსებობს დაჭერა.
რა არის ვარაუდი, რომ ჩვენ თავისთავად ბინარული ძიება?
აქვე უნდა გადანაწილებული.
ეს არ გადანაწილებული, შეგიძლიათ გაყოფილი რამ ნახევარი ისევ და ისევ, და თქვენ
შეიძლება დაუტოვებიათ, და შეგიძლიათ უფლება, და შეგიძლიათ მარცხენა და მარჯვენა, მაგრამ თქვენ
არ აპირებს მოვძებნოთ ელემენტს თუ სიაში არ არის გადანაწილებული, რადგან
თქვენ შეიძლება გამოგრჩეთ ეს.
რადგან თქვენი heuristic, რადგან მიმდინარეობს მარცხენა ან მარჯვნივ უნდა გაყალბდა თუ ეს
მართლაც არ გადანაწილებული.
ასე რომ ერთგვარი ფარული ღირებულება გამოყენებით მსგავსი რამ.
>> ახლა მოდით წასვლას ჩვენი დახარისხება ალგორითმები არ ეძებს -
oh, ფაქტობრივად, მოდით წავიდეთ ამ ცარიელი.
ორობითი ძებნის საუკეთესო შემთხვევაში?
ეს ასევე 1 თუ უბრალოდ ხდება, ძალზე შუა მასივი, ან
შუა სატელეფონო წიგნი.
ახლა ამის გაკეთება bubble sort.
ასე რომ, კიდევ ერთხელ, ახლა ჩვენ შესვლისას სახის, არ ეძებს.
>> უარეს შემთხვევაში, რამდენი ნაბიჯები მივიღეთ სარჩელი bubble sort აპირებს მიიღოს?
n კვადრატში.
ამიტომ, მე ვაპირებ შევაჩერო, რომ.
Ooh, ჩემი ხელწერა გამოიყურება უარესი როდესაც ის დაპროექტებული, რომ დიდი.
ყველა უფლება.
ასე რომ, n კვადრატში.
და საუკეთესო შემთხვევაში, bubble sort, რამდენი ნაბიჯები იგი აპირებს?
1, გავიგე.
>> დინამიკები 1: n.
>> დევიდ ჯ Malan: n, გავიგე.
>> დინამიკები 1: 2.
>> დევიდ ჯ Malan: 2, გავიგე.
ნუ მესმის 3?
ყველა უფლება.
ასე რომ მე მოვისმინე 1, N 2, მაგრამ გააშუქა გარდა, სულ მცირე, პირველი იმ
წინადადებები, 1.
ეს არ არის ცუდი ინსტიქტი, რადგან ეს სახის შემდეგნაირად ნიმუში აქ.
მაგრამ თუ ეს მხოლოდ იღებს 1 ნაბიჯი, თუნდაც მსოფლიოში ვერ I აცხადებენ, რომ სიაში
ინახება, რადგან თუ მე ნებადართულია მხოლოდ მიიღოს 1 ნაბიჯი, რამდენი ელემენტები
შეიძლება მე რეალურად შესამოწმებლად დარწმუნებული უნდა იყოს?
ისე, მხოლოდ 1, რაც ნიშნავს, რომ არსებობს n მინუს 1 ელემენტს, რომლებიც შესაძლოა იყოს გარეთ
იმისათვის, და მე მხოლოდ მიმდინარეობს რწმენის შემდეგ ეძებს 1 ელემენტი, რომელიც
რამ ინახება.
ამგვარად 1 არ გამოსწორებას აქ.
ასე რომ, მინიმუმ, რამდენი მაქვს, რომ შევხედოთ?
>> [INTERPOSING ხმები]
>> დევიდ ჯ Malan: N მინუს 1, ან მართლაც, ნ, იმიტომ, რომ მე უნდა შევხედოთ ყველა
ელემენტს დავრწმუნდეთ, რომ ეს არ არის მწყობრიდან.
თუმცა ისევ და ისევ, ჩვენ ერთგვარი ტალღა ჩვენი ხელში პატარა ნომრები და
ვივარაუდოთ, რომ, როგორც ო იღებს დიდი, ისინი უინტერესო მაინც.
ასე რომ, bubble sort.
ახლა კი, მოდით ეს ბოლო ორი.
შერჩევა დალაგების, და შემდეგ ჩვენ გამოგიგზავნით ამის გაკეთება ჩანართი ჯიშია.
და მაშინ ჩვენ აფეთქება თქვენი გონებაში რაღაც ბევრად
უკეთესია, ვიდრე ყველა მათგანი.
ყველა უფლება.
>> რა არის უარეს შემთხვევაში გაშვებული დრო შერჩევა ერთგვარი?
>> დინამიკები 4: n კვადრატში.
>> დევიდ ჯ Malan: N მოედანი, მე მოსმენა.
მაგრამ რატომ n კვადრატში, ინტუიციურად?
>> დინამიკები 4: იმის გამო, რომ ჩვენ უბრალოდ ეს გააკეთა.
>> დევიდ ჯ Malan: იმის გამო, რომ ჩვენ უბრალოდ ეს გააკეთა.
OK.
კარგი პასუხი.
მაგრამ ინტუიციურად, რატომ არის შერჩევა დალაგების n კვადრატში?
რა უნდა გავაკეთოთ ისევ და ისევ?
ჩვენ უნდა შევინარჩუნოთ სკანირების მეშვეობით, რომლებიც თქვენ ყველაზე პატარა, თქვენ
პატარა, ხარ პატარა.
და გაცემული, ჩვენ შევძელით მიიღოს ო ნაბიჯებს, მაშინ n მინუს 1, მაშინ n მინუს 2.
მაგრამ თუ ასეთი დავამატებთ იმ მა ან მას არ მონაწილეობს რწმენა, რომ მე დასძინა
მათ წინასწარ, მივიღებთ დაახლოებით n squared მინუსი ზოგიერთი უფრო პატარა ნომრები.
ამიტომ, მე ვაპირებ მოვუწოდო ამ n კვადრატში.
მაგრამ შერჩევა ერთგვარი საუკეთესო იმ შემთხვევაში, თუ რამდენი ნაბიჯები არის ეს
აპირებს მე?
>> დინამიკები 5: [inaudible]
>> დევიდ ჯ Malan: ეს, სამწუხაროდ ჯერ კიდევ n კვადრატში, არა?
იმიტომ, რომ თუ მე შერჩევისას ყველაზე პატარა ელემენტს, და ჩვენ შვიდი ადამიანი აქ,
მე მხოლოდ ვიცი, ერთხელ მოხვედრა ძალიან საბოლოოდ, რომ მე ი პატარა
ნომერი, ნებისმიერ სიტუაციაში ან მან შეიძლება ყოფილიყო.
მაგრამ როგორ მოვძებნო შემდეგი ყველაზე პატარა ნომერი?
მე უნდა გავაკეთოთ კიდევ ერთი უღელტეხილი.
ასე რომ, საუკეთესო შემთხვევაში, რა არის შეყვანის შერჩევის დალაგების?
ეს უკვე ერთგვარი სია, ნომერ, მეორე, მესამე, ნომერი ოთხი.
მაგრამ მე კომპიუტერში.
მე შემიძლია მხოლოდ ვუყურებდეთ რამ დროს.
მე ვერ ერთგვარი მიიღოს ნაბიჯი უკან ისევე როგორც ადამიანის და აცხადებენ,
Ooh, ეს გამოიყურება სწორი.
>> მე შემიძლია მხოლოდ განიხილავს სისწორის in შერჩევა ერთგვარი შერჩევით
ყველაზე პატარა ნომერი.
თუმცა, მე ნომერ პირველი, თუ მე არ ვიცი არაფერი შესახებ
სხვა ნომრები, რომელიც მე არ, ყველა მე ვიცი, რომ მე გადაეცა მასივი
ან კომპლექტი კარი უკან, რომლებიც ციფრები, ერთადერთი გზა, მე ვიცი, რომ ერთი
იყო პატარა?
თუ მივიღებ ყველა გზა აქ და გააცნობიეროს, რა, ერთი მართლაც პატარა.
>> მაგრამ როგორ შემიძლია შემდგომში გადაწყვეტს, რომ ორი არის მომავალი პატარა?
ამით იგივე არაეფექტურობა ისევ და ისევ.
საბოლოოდ, ერთად Insertion დალაგების, როგორ, უარეს შემთხვევაში,
საერთოდ ვამბობთ ასრულებს?
ეს ესეც n კვადრატში.
და რა საუკეთესო შემთხვევაში?
ჩვენ დავტოვებთ, რომ როგორც cliffhanger.
ჩვენ ამის შევსება, რომ ცარიელი მომავალში, მაგრამ პირველი ნება მომეცით შესთავაზოს, რომ ჩვენ
ფუნდამენტურად ამის გაკეთება უკეთესია, ვიდრე ყველა ჩამოთვლილი, ყველა უფლება?
>> ასე რომ, ვფიქრობ, თავს რა ჩასაგდები დალაგების იქნება.
ისე, რომ არ იყო ძალიან დრამატული, რადგან მე მხოლოდ ერთი
რომ დაინახა ცვლილება.
Wow.
OK.
ასე რომ, აქ ჩვენ გვაქვს გარკვეულწილად სხვადასხვა დემონსტრირება.
თუ მე გასადიდებლად აქ, თქვენ ნახავთ, რომ მარცხენა გვაქვს bubble sort, ამ
შუა გვაქვს შერჩევის დალაგების, და შორს უფლება, ჩვენ გვაქვს რაღაც ჩვენ
არ შევხედე ჯერ კიდევ მოუწოდა შერწყმა სახის.
მაგრამ რა ჩვენ აკეთებს აქ დღემდე იმყოფება.
როდესაც ჯენიფერი პირველად გამოვიდა სცენაზე, ჩვენ გაიარა მასივი ნომრები
ერთხელ, და კიდევ ერთხელ წრფივი ძებნა, და მივიღეთ წრფივი ქრონომეტრაჟი, დიდი O
საქართველოს ო, ასე ვთქვათ.
>> როდესაც ჩვენ განვიხილოთ პირველ კვირას კლასის, როცა ჩვენ გვქონდა გათიშე და დაპყრობას,
და ჩვენ რომ სატელეფონო წიგნი tearing, და ჯენიფერი და ჩვენ ერთობლივად
leveraged რომ მთავარი ქათამაძე, რომელიც ვიმეორებ თავს ისევ და ისევ
რატომღაც სროლა მოშორებით, სროლა მოშორებით, სროლა მოშორებით, ნახევარი პრობლემა, ან
ზოგადად, გამყოფი პრობლემა ნახევარი, ხოლო შემდეგ მკურნალობის პატარა ნატეხი
პრობლემა, როგორც კონცეპტუალური ექვივალენტს მეორე, ჩვენ როგორღაც გააკეთა
ფუნდამენტურად უკეთესი.
მაგრამ bubble sort, რომლის შერჩევა დალაგების, ერთად Insertion დალაგების, ჩვენ შეუძლია
ასეთი მოსაზრება, რომ ჯენიფერი გააკეთა.
ჩვენ საკმაოდ ბევრი უბრალოდ დადიოდა და უკან მეოთხე მთელი bunch of ჯერ, და ჩვენ
tweaked რამ ცოტა, შევცვალე ამ მიზნით, შესაძლოა,
ჩასმის ან შერჩევით.
თუმცა, დღის ბოლოს, მე ბევრი საქართველოს უხერხულ სიარულის უკან და სხვა.
ჩვენ ნამდვილად არ ბერკეტები რაღაც ჭკვიანი, როგორიცაა Jennifer გააკეთა მსგავსად გამყოფი
და დაპყრობის.
>> ასე რომ შერწყმა დალაგების, პირიქით, რაც ჩვენ ვერ ვხედავ, სანამ მომავალ კვირას, ის აპირებს
to ბერკეტი, რომ მთავარი იდეა მიერ გამყოფი შეყვანა, შემდეგ კი საჯელის განახევრებას, შემდეგ კი
საჯელის განახევრებას, შემდეგ კი საჯელის განახევრებას.
და თითოეულ iteration რომ მარყუჟის დახარისხება მარცხენა ნახევარში და უფლება
ნახევარი, მაშინ მარცხენა ნახევარში მარცხენა ნახევარში, და მარჯვენა ნახევარში მარცხენა, მაშინ
მარცხენა ნახევარში მარჯვენა ნახევარში და მარჯვენა ნახევარში მარჯვენა ნახევარში.
და იმეორებს ისევ და ისევ.
>> ასე რომ, თქვენ ნახავთ ამ ვიზუალურად, მაგრამ ეს არის ის, რაც გველოდება მომავალ კვირას.
და საერთოდ, როცა ჩვენ ვფიქრობთ, პატარა ცოტა უფრო რთული ასეთი ხასიათის პრობლემას.
ჩვენ n კვადრატში მარცხენა ო squared ცენტრიდან, და N
სისტემიდან ო მარჯვენა.
ასე რომ თქვენი რეალური cliffhanger.
ჩვენ დავინახავთ, თქვენ ორშაბათს.
>> [ტაში]