[მუსიკის დაკვრა] დევიდ ჯ Malan: ეს არის CS50. და ეს არის დაწყების კვირაში სამი. ამიტომ, ჩვენ მივიღეთ ბევრი საინტერესო რამ დასაფარავად დღეს. ბევრი შესაძლებლობები მოხალისეები სცენაზე. და ბოლოს, დღეს არის არ გაუშვა კოდი ყველა. მაგრამ ეს იდეები, და ეს დაახლოებით ალგორითმები, და რეალურად დააბრუნონ ზოგიერთი გაკვეთილების კვირის ნულოვანი, სადაც გავიხსენოთ, ჩვენ გააცნო ამ monstrosity. და სესხების შთაგონების აქედან გამომდინარე, უნდა დაიწყოს მოგვარება უფრო დახვეწილი პრობლემა ალგორითმულად. მაგრამ პირველი, რამდენიმე განცხადებები. ასე რომ, ერთი, თუ გსურთ შეუერთდება CS50 პერსონალი და თანაკლასელები ლანჩი ამ პარასკევს, როგორც აქ და კემბრიჯის და New Haven, გთხოვთ, ეწვიოთ რა თქმა უნდა, ნახვა, სადაც URL გვხვდება. ლექცია ამ ოთხშაბათს არ შეიძლება აქ Sanders. ეს იქნება მხოლოდ, ასე რომ, სრულყოფილი at CS50 ნახვა, თუ არა აქ Cambridge ან New Haven ისევე. და მაშინ პრობლემა მითითებული ორი უკვე თქვენს ხელშია. თუ არ საპირისპირო არ არის, ნება მიბოძეთ შესთავაზოს მკაცრი წინადადება რომ, განსაკუთრებით ახლა, რადგან პრობლემა კომპლექტი წინასწარ, თქვენ ნამდვილად არ მინდა, რომ დაიწყოს, თუ არა dabble ცოტა შაბათ ან ადრე როდესაც ისინი პირველად წასვლა გარეთ პარასკევს, იმიტომ, რომ თქვენ ნახავთ, რომ ისინი არ ემთხვეოდეს მიღების აღარ და უფრო რთული პოსტი se. მე ვფიქრობ, რომ თქვენ იპოვით, რომ ზოგადად, ისინი, როგორც წესი, მიიღოს უხეშად დაახლოებით იმავე დროის. მაგრამ ეს, რა თქმა უნდა დამოკიდებულია სტუდენტი, და ეს დამოკიდებულია აზროვნების რომელიც თქვენ მივუდგეთ მას. მაგრამ ყოველთვის, თქვენ აპირებს აწარმოებს წინააღმდეგ ზოგიერთი კედელი, და თქვენ ვაპირებთ მოხვდა ზოგიერთი bug, და თქვენ მხოლოდ არ აპირებს შეძლებს მიიღეთ მეტი რაღაც მომენტში. და ეს უკიდურესად ღირებული შეძლებს დახევას დაშორებით, დავბრუნდებით მეორე დღეს, წასვლა საათებში, პოსტ on CS50 იმსჯელებს ან მოსწონს, რომ რეალურად მიიღონ ბლოკი. გააგრძელეთ, რომ გონება. დასაწყისი ადრეული, რაც შეიძლება არის საუკეთესო რამ შეგიძლიათ გააკეთოთ. ასე რომ, აქ, სადაც ჩვენ დავიწყეთ კლასის, მეტი კვირაში ნულოვანი. და შეგვიძლია მოხალისე აქ დამეხმარება იპოვოს mics? OK. მუდმივმოქმედი უკვე. კარგით up. ვხვდები, რომ ის, თუ როგორ იმუშავებს. რა გქვია? ALAN ESTRADA: Alan Estrada. დევიდ ჯ Malan: ალან Estrada. კარგით up. კარგია თქვენთან შეხვედრა. ALAN ESTRADA: კარგია თქვენთან შეხვედრა. დევიდ ჯ Malan: და იყო აქ ჩვენთან კვირაში ნულოვანი, რა თქმა უნდა. ALAN ESTRADA: მე ვიყავი. მე ვიყავი. დევიდ ჯ Malan: ასე რომ, შეიძლება თქვენ გადასვლა წინ და ჩვენთვის მაიკ სმიტი, როგორც სწრაფად, როგორც თქვენ შეგიძლიათ? როგორც სწრაფად, როგორც თქვენ შეგიძლიათ. სიტყვასიტყვით tearing პრობლემა ნახევარი, როგორც თქვენ უნდა. ALAN ESTRADA: Um. დევიდ ჯ Malan: სიტყვასიტყვით tearing პრობლემა ნახევარი. ALAN ESTRADA: Oh. Mm. ძალიან კარგი. დევიდ ჯ Malan: OK. კარგი. დიდი მადლობა. ALAN ESTRADA: ძალიან კარგი. OK. დევიდ ჯ Malan: ასე რომ, ახლა, თქვენ გახდნენ ის ქვემოთ ნახევარი ზომის პრობლემა. ახლა, ჩვენ ქვემოთ კვარტალში. თქვენ გადამხდელი ყურადღებას რომელ მხარეს ჩვენ შენახვა? [იცინის] ALAN ESTRADA: დიახ, ვფიქრობ დევიდ ჯ Malan: რა მონაკვეთზე ვართ ჩვენ? ALAN ESTRADA: კაშნეები, ასე. დევიდ ჯ Malan: OK. მაგრამ მაიკ სმიტი აპირებს უნდა იყოს შემდეგ კაშნეები. ასე რომ-- [იცინის] ყველა უფლება. ALAN ESTRADA: სად ჩვენ ვეძებთ? დევიდ ჯ Malan: მაიკ სმიტი. ALAN ESTRADA: მაიკ სმიტი. დევიდ ჯ Malan: ახლა, ჩვენ ქირურგიული. ახლა, ექიმები. ახლა კი ALAN ESTRADA: Let's- მოდით წავიდეთ ერთად რეალური. უძრავი. დევიდ ჯ Malan: უძრავი. OK. თუ თქვენ გჭირდებათ რეალური. ახლა, რაც გზა არის მაიკ სმიტი? ALAN ESTRADA: ეს გზა. დევიდ ჯ Malan: რომელი გზა? ALAN ESTRADA: Wait. M is-- უფლება? ჩვენ დავიწყეთ with-- დევიდ ჯ Malan: ჰო. ისინი დატოვა. თქვენი მარჯვენა. ALAN ESTRADA: ჰო. დევიდ ჯ Malan: ასე რომ, მაიკ აქ. ALAN ESTRADA: რა? [იცინის] Bad მაგალითად, ბიჭები. ბოდიში. დევიდ ჯ Malan: ეს შეასწავლიან თქვენ ნახტომი თქვენი თავმჯდომარე. ALAN ESTRADA: Oh. Oh. მე თქვენ. მე თქვენ. Oh. Oh. ეს is-- OK, მე თქვენ. Smith უფლება აქ? დევიდ ჯ Malan: Smith, მადლობა. ასე რომ, მე შენარჩუნება ეძებს სმიტი? ALAN ESTRADA: Oh, yeah. არა, არა, არა. ო, არა. ეს ჩემია. დევიდ ჯ Malan: Oh, შენ სმიტი. OK. ALAN ESTRADA: ჰო, მე მიიღო Smith უფლება აქ. უკაცრავად, ბიჭები. ვფიქრობდი, Michael-- ჩვენ ეძებს Michael. ბოდიში. დევიდ ჯ Malan: ეს არის OK. ყველა უფლება, ახლა ჩვენ შევიდა Paccini და შვილები. ALAN ESTRADA: Paccini და შვილები. დევიდ ჯ Malan: მხოლოდ თქვენ და მე ვართ ამ. OK. გვიპოვეთ მაიკ სმიტი. სმიტი. ALAN ESTRADA: სმიტი. დევიდ ჯ Malan: სმიტი. ჩვენ ვართ R ნაგავსაყრელად. ALAN ESTRADA: ნაგავი. Oh. ეს აპირებს ხნით. [იცინის] დევიდ ჯ Malan: ფეხსაცმელი. ჩვენ ფეხსაცმელი. ALAN ESTRADA: ახლა ჩვენ gonna-- დევიდ ჯ Malan: Nice. ALAN ESTRADA: Which-- [იცინის] ოჰ, ეს არის დიდი. [იცინის] დევიდ ჯ Malan: ეს არის OK. ALAN ESTRADA: ოჰ, ეს არის კარგი. მე არ ვფიქრობ, მე ვაპირებ აქვს PSAT მეგობრებთან შემდეგ. დევიდ ჯ Malan: კარგი. სპორტული. ALAN ESTRADA: სპორტული. Um, L, M, N, O, P. დევიდ ჯ Malan: OK. მოდით გაანადგურეს ამ ნახევარი. ეს OK. ეს დამთავრდა ცუდად მაინც, რადგან Mike Smith არ იქნება ყვითელი გვერდები. ALAN ESTRADA: Aw. დევიდ ჯ Malan: არა, ეს OK. მაგრამ მოდით პრეტენზია მოსწონს ის ამ გვერდზე. ასე რომ, ახლა თქვენ გახდნენ პრობლემა ქვემოთ ერთ გვერდზე და აღმოვაჩინეთ მაიკ სმიტი. [Cheering] OK, მადლობა. OK. ეს იყო საოცარი. მაგრამ ეს იყო კიდევ უფრო სწრაფად ვიდრე სწორხაზოვანი ძებნა, სადაც ჩვენ იწყება დაწყებული წიგნი, და ჩვენ გადაადგილება ჩვენი გზა მარცხნიდან მარჯვნივ, საბოლოოდ ეძებს მაიკ სმიტი. ასე რომ, თუ სატელეფონო წიგნი ჰქონდა, შესაძლოა, 1000 გვერდების, შესაძლოა, ეს იქნებოდა მიღებული ჩვენს 10 ან იმდენად გვერდი ცრემლები. მაგრამ თქვენ არ leveraged შეეხო ვარაუდი, დროს ყველა, რომ, რომელიც, შეიძლება ითქვას, რომ სატელეფონო წიგნი წინასწარ რა? აუდიტორია: დალაგებულია. დევიდ ჯ Malan: ეს დახარისხებული. მარჯვენა? ეს დალაგებულია ალფავიტის, ასე რომ რომ ყველა იმ სახელები და ნომრები დალაგებულია საწყისი A- ს რომ Z, და ალფავიტის შორის. მაგრამ დღეს, ჩვენ ახლა ითხოვენ კითხვაზე, ასევე, როგორ გააკეთა Verizon ან ტელეფონი კომპანია მიიღოს იგი, რომ სახელმწიფო? იმიტომ, რომ ეს არის ერთ ერთი რამ ბერკეტი რომ ვარაუდი და, შესაბამისად, პრობლემის გადაჭრას რომელზეც ალგორითმი უფრო ეფექტურად. მაგრამ ჩვენ არასდროს ნამდვილად კითხვაზე, კვირაში ნულოვანი, ასევე, რამდენად ეს გააკეთა ღირებულება Verizon თუ ვინმე სხვა მიიღოს, რომ სატელეფონო წიგნი დახარისხებული მიზნით? მარჯვენა? არ აქვს მნიშვნელობა, თუ ეძებს მაიკ სმიტი სუპერ სწრაფი, თუ ის მოგაწვდით წელი დასალაგებლად გვერდები თავდაპირველად. მარჯვენა? თქვენ შესაძლოა, ასევე უბრალოდ sift მეშვეობით რანდომიზებული სატელეფონო წიგნი, თუ ეს იქნება სუპერ ძვირადღირებული დასალაგებლად ის. ასე რომ, თუ შეიძლება კიდევ ერთი მოხალისე. ავიღოთ ეძებოთ აქ როგორ ჩვენ might-- მოდის შესახებ up-- როგორ ჩვენ შეიძლება წავიდეს დახარისხება ეს. და თუ Jordan შეიძლება რეალურად შემოგვიერთდნენ აქ სცენაზე. ამოდით მხოლოდ ერთი წუთით. რა გქვია? CAROLINE: Caroline. დევიდ ჯ Malan: Caroline, მოდის up. და თქვენ უნდა შეუერთდა მე და იორდანიის აქ. Caroline, მადლობა. ყველა უფლება. რა გვაქვს აქ Caroline 26 ლურჯი წიგნები რომ FAS იყენებს ადმინისტრირება გარკვეული საბოლოო გამოცდები. ეს იღებენ უჭირს, მაგრამ, რაც ჩვენ გავაკეთეთ წინასწარ ის არის, რომ ჩვენ დააყენა ვინმეს სახელი ფრონტის თითოეული ამ, მაგრამ ჩვენ ინახება ეს მარტივი მაშინ აყენებს სრული სახელები. ასე რომ, ჩვენ დააყენა პირს სახელით L, D, J, B, ყველა გზა მეშვეობით Z, მაგრამ ისინი შემთხვევითი მიზნით. ასე რომ, თუ გვინდა, საუბარი თქვენი გზას პრობლემა, როგორც თქვენ ამის გაკეთება, შეგიძლიათ წავიდეთ წინ და დასალაგებლად ამ ჩვენთვის, რომ ზ აუდიტორია: OK, ასე L ჰგავს, შუა. C იწყება. ბ J ადრე L. B, Q. დევიდ ჯ Malan: გამართავს, რომ ეგონა, ერთი მეორე. რადგან, წინააღმდეგ შემთხვევაში, ეს მხოლოდ საინტერესოა, რომ თქვენ, მე, და იორდანიაში. იქ ჩვენ წავიდეთ. აუდიტორია: [INAUDIBLE]. რ დევიდ ჯ Malan: OK. რას აკეთებ? CAROLINE: M მას შემდეგ O. დევიდ ჯ Malan: OK. CAROLINE: ო დევიდ ჯ Malan: O, კარგი. CAROLINE: E. დევიდ ჯ Malan: E, F. ჰო. CAROLINE: T, U, ვ დევიდ ჯ Malan: V, T, U, V. ასე რომ, ჰგავს თქვენ making-- შენარჩუნებას აპირებს. როგორც ჩანს, თქვენ მიღების დიდი წყობის აქ, და სახის დიდი წყობის იქ. ასე რომ, პირველ ნახევარში ანბანი, მეორე ნახევარში ანბანი. OK. კარგი. კეთილი გაყოფის პრობლემა ორი. M, N, X. ჰო. CAROLINE: კ დევიდ ჯ Malan: OK. კ ასე რომ თქვენ სახის შერჩევის მათ ერთმანეთის მიყოლებით, აყენებს მას ან მარცხნივ ან მარჯვნივ, ან Z აპირებს იატაკზე. OK. CAROLINE: Z ხდება სართული. დევიდ ჯ Malan: OK. Y აპირებს იატაკზე. ახლა ჩვენ შეგვიძლია X. CAROLINE გ დევიდ ჯ Malan: G ის აპირებს მარცხენა. S აპირებს უფლება. ყველა უფლება, A აპირებს ყველა გზა დარჩა. CAROLINE: A, B, C, D. დევიდ ჯ Malan: ახლა, კარგი. ჩვენ მივიღეთ A, B, C. W აპირებს ქვემოთ. ყველა უფლება, T. CAROLINE: H, I, J. დევიდ ჯ Malan: H, I, J. კარგი. CAROLINE: ცენტრში, მე gonna-- დევიდ ჯ Malan: OK. ახლა, ჩვენ ვაპირებთ სახის საქართველოს შერწყმა ამ სხვადასხვა piles. ასე რომ მეშვეობით C, მაშინ მე ვერ ვხედავ D და E და F და G და H, და ი Nice. J, K. და შემდეგ, ამ წყობის თავდაყირა, მაგრამ რომ კარგადაა. რა თქმა უნდა. ჩვენ შეგვიძლია მოჭრილი ზოგიერთ კუთხეში. OK. და მაშინ ჩვენ უნდა W, X, Y, ზ CAROLINE: ჰო. დევიდ ჯ Malan: შესანიშნავი. ასე რომ, დიდი მადლობა Caroline დახარისხება ეს. [Cheering] დიდი მადლობა. ძალიან დიდი მადლობა. ახლა მოდით დავფიქრდეთ როგორ Caroline წავიდა აკეთებს, რომ, და რა ჩვენ შეძლეს, რომელთა მიზანია, თუ როგორ შეძლეს გადაწყვიტოს, რომ პრობლემა, როდესაც ჩვენ მხოლოდ მოცემული მთელი bunch of შემთხვევითი საშუალებებით. ისე, როგორც ჩანს, არ იყო ცოტა სისტემაში? უფლება. ასე რომ, ადრე წერილები ანბანი, მან იყო გამოსული მარცხენა, და შემდეგ ასო ანბანი, იგი აყენებს უფლება. და როგორც კი მან აღმოაჩინა ზოგიერთი პროქსიმალური წერილები, პირობა რომ წავიდეს უფლება შემდეგი ერთმანეთს, იგი დააყენა იმ მიზნით. ასე რომ, ჩვენ სახის ჰქონდა ეს პატარა piles დახარისხებული საშუალებებით ხდება. და ისე, რომ საკმაოდ მსგავსად, რაც ყველაზე მეტად ჩვენს ადამიანები ყველაფერს გააკეთებს. ჩვენ იქნებოდა ერთგვარი Sift მეშვეობით მას, და ჩვენ გვინდა სახის აქვს მექანიზმი. მაგრამ ეს შეიძლება იყოს რთული დაწერა ის ქვემოთ ფორმულა თავისთავად. იგი გრძნობდა, ცოტა მეტი ორგანული, ვიდრე. მოდით ვნახოთ, თუ ჩვენ შეგვიძლია შეკრული პრობლემა ნაკლები საშუალებებით. იმის ნაცვლად, რომ 26, მოდით ამის გაკეთება რაღაც ბევრად უფრო ნაკლები მხოლოდ ამბობენ, შვიდი, უკან ამ კარს, ასე ვთქვათ. არსებობს მხოლოდ შვიდი ნომრები? და თუ მიზანი ახლა მხრივ არის ის, რომ მნიშვნელობა, ვნახოთ, როგორ ეფექტურად ჩვენ შეგვიძლია წავიდეთ შესახებ აკეთებენ. მოდით ვნახოთ, თუ ჩვენ ახლა დაიწყება მიმართოს ზოგიერთი ნომრები, ან რაღაც ფორმულები, რომელიც აღწერს ეფექტურობის ჩვენი სატელეფონო წიგნი ალგორითმი, ჩვენი გამოცდა წიგნაკი ალგორითმი და უფრო ზოგადად, ინფორმაციის მოძიება. ასე რომ, ეს, ნება მომეცით წავიდეთ წინ და სენსორული აქ, ბოლო ბრაუზერი, რომელსაც აქვს სწორედ ამ შვიდი კარი. და თუ ჩვენ ვერ ერთი სხვა მოხალისე მოვა აქ, მე დააყენა ეს იგივე კარ აქ. სწრაფი მოხალისე. ეს ერთ demos ვაპირებთ უფრო სწრაფი და უფრო სწრაფად, ახლა. კარგით ქვემოთ. რა გქვია? TREVOR: Trevor. დევიდ ჯ Malan: Trevor? ყველა უფლება, Trevor, მოდის ქვემოთ. ასე რომ, Trevor აქვს მოხალისეებად აქ ამის მსგავსი პრობლემა, მაგრამ ერთი, რომ ვიწრო ფარგლებს, და რომ აპირებს საშუალებას გვაძლევს ცდილობენ ოფიციალურად ახლა პროცესი დახარისხება ამ ნომრებზე. ასე რომ, Trevor, კარგია თქვენთან შეხვედრა. ასე რომ, აქ არის მასივი, ასე ვთქვათ, სიაში შვიდი კარი. წავიდეთ წინ და იპოვოს ჩვენს ნომერი 50. და შემდეგ, ფაქტობრივად, გვეუბნებიან, თუ თქვენ ვერ. თუ be-- ყველა უფლება. ჰო, ეს არის ერთ-ერთი აქ? Uh-oh. OK. თქვენ აირჩიეთ, რომ ერთი. კარგი. და კარგი. ახლა თქვენ აირჩიეთ, რომ ერთი. და ნება მომეცით, მიკროფონი, ისე, რომ თქვენ გაქვთ ეს მხოლოდ ერთი წუთით. წავიდეთ წინ და დააჭირეთ მეზობლად, რომ თქვენ აპირებთ. დიახ, კარგი. TREVOR: შემიძლია unclick კარი? დევიდ ჯ Malan: არა, თქვენ ვერ unclick. TREVOR: OK. ეს ერთი. დევიდ ჯ Malan: სად გინდა წასვლა? რომელი? TREVOR: ეს ერთი. დევიდ ჯ Malan: No. TREVOR: OK. ეს ერთი. დევიდ ჯ Malan: დიახ. ეს იყო კარგი. ყველა უფლება. ასე რომ, რა იყო თქვენი ალგორითმი ან პროცედურა ამით, Trevor? TREVOR: უბრალოდ გაიარა კარი სანამ ი 50. დევიდ ჯ Malan: OK. შესანიშნავი ალგორითმი. ასე რომ, ჯარიმა. იმის გამო, რომ ის ფაქტი, რომ, თუ მე გამოვლენა, თუ რა არის უკან ამ ორი სხვა კარები, რა ჩვენ იპოვით აქ ის არის, რომ ჩვენ მხოლოდ შემთხვევითი შეყვანა. ასე რომ, ფაქტობრივად, როგორც კარგი, როგორც თქვენ შეიძლება მიიღოთ. და სინამდვილეში, თქვენ გაქვთ უკეთესი, ვიდრე ამომწურავად ძებნას მთელი მასივი, იმიტომ, რომ ეს იქნებოდა მართლაც უიღბლო თუ მოხვდა ნომერი 50 ძალიან ბოლო კარი. მაგრამ თუ ჩვენ ნაცვლად მისცა თქვენ ვარაუდი. დავუშვათ, რომ ერთგვარი ყველა ამ კარს გარშემო, ასე, რომ თქვენ გაქვთ ნომრები დახარისხებული ამ დროს, მაგრამ ამ დროს ის, ფაქტობრივად, different-- ამ დროს, ეს რეალურად დახარისხებული თქვენთვის. და ახლა მიზანი ხელთ მოხვდა ნომერი 50. TREVOR: OK. დევიდ ჯ Malan: რა არის თქვენი ალგორითმი იქნება? TREVOR: ისე, თუ ეს დალაგებულია, ეს არც აპირებს რომ იყოს, თუ დიდი, რომ დიდი, დაღმავალი, ეს იქნება პირველი, თუ ეს, პირიქით, ეს იქნება ბოლო ერთი. ასე რომ, მე მხოლოდ ლიბერალიზაცია ეს კარი და მაშინ მხოლოდ ლიბერალიზაცია ბოლო კარი. დევიდ ჯ Malan: შესანიშნავი. ყველა უფლება. ასე რომ, ჩვენ აღმოვაჩინეთ ნომერი 50. ამიტომ, როგორც კი თქვენ იცოდა ისინი დახარისხებული, ჩვენ შეძლეს ბერკეტები ამ მოსაზრებას. ასე რომ, ისინი ძალიან ჰგავს სატელეფონო წიგნი მაგალითად. როგორც კი თქვენ გაქვთ, თუნდაც პატარა პრობლემა, როგორც ეს, თქვენი საშუალებებით წინასწარ გადანაწილებული, ჩვენ შეგვიძლია რეალურად ღირებულება სავარაუდოდ უფრო ეფექტურად. და მე არ გეტყვით, იყო თუ არა ეს დალაგებულია პატარა დიდი, ან დიდი, პატარა, და ასე, რომ ეს იყო ძალიან გონივრული დაიწყოს ერთ ბოლოს ან მეორე რეალურად ნახავთ, რომ სამიზნე ღირებულება. ასე რომ მადლობა ტრევორ ისევე. და მე შესთავაზოს ლამაზად კეთდება. ჩვენ გვყავს პატარა კლიპი, ფაქტობრივად, მათ შორის არის ჩვენი საყვარელი მომენტები CS50, რომლის დროსაც ზოგჯერ ეს demos არ საკმაოდ წასვლა გეგმის მიხედვით. და მართლაც, ახლა, მე გამოყვანილია არასწორი ინტერფეისი , რომლის გამოყენება სენსორული. ასე რომ, ჩემი ბრალი იყო. ასე რომ, ეს გახდის მომავალი წლის კლიპი როგორც რატომ მე დაჭერით ჩემს ეკრანზე. მაგრამ მოდით მიიღოს სწრაფი შევხედოთ რა მოხდა გასულ წელს ჯეი, რომელიც გამოვიდა, ბევრი მოსწონს Trevor აქ, მოხალისეებად, და ამ მოკლე კლიპი, დაინახავთ როგორ იგივე დემო არ საკმაოდ გამოვლენა იგივე გაკვეთილები. [ვიდეო აღწარმოების] -ყველა მე მინდა, რომ ახლა არის იპოვოს ჩემთვის და ჩვენთვის, მართლაც, ნომერი 50 ერთი ნაბიჯი დროს. -The ნომერი 50? -The ნომერი 50. და თქვენ შეგიძლიათ გამოვლენა, თუ რა არის უკან თითოეულ ამ კარი უბრალოდ ეხება ეს თითი. რა იგი. [იცინის] [END აღწარმოების] დევიდ ჯ Malan: ასე რომ წავიდა ძალიან კარგად. ისინი იყვნენ დაუხარისხებელი კარი. ჯეი და, რა თქმა უნდა, აღმოჩნდა, რომ ეს ყველაფერი ძალიან სწრაფად. Trevor გააკეთეს ბევრად უკეთესი სამუშაო თვალსაზრისით teachable მომენტში, ასე ვთქვათ, ამ წელს აღების უფრო მიაგნეს. რა თქმა უნდა, ჩვენ მათ Jay მეორე შანსი, რომლის დროსაც ჩვენ დახარისხებული კარი, ისევე როგორც ჩვენ გავაკეთეთ Trevor, და ტრევორ გააკეთა სუპერ კარგად ამ დროს. მაგრამ Jay ეს გააკეთა ნახევარი, რაც შეიძლება. [ვიდეო აღწარმოების] -The მიზანი არის ის, რომ ასევე მოგვაგნოთ ნომერი 50, მაგრამ ამის გაკეთება ალგორითმულად და გვეუბნებიან, თუ როგორ ვაპირებთ ამის შესახებ. -OK. ისე, თავად თუ ის, თქვენ გაქვთ ფილმი. თუ არ მიაგნეს, თქვენ მისცეს მას უკან. -man. -Oh! - [INAUDIBLE] OK. ამიტომ, მე ვაპირებ, რათა შეამოწმოს მთავრდება პირველი, რათა დადგინდეს, თუ there's-- Oh. [ტაში] [END აღწარმოების] დევიდ ჯ Malan: OK. ასე რომ, დახარისხება კარი აშკარად იწვევს უფრო მეტი ეფექტურობა. ასე რომ, ორჯერ სწრაფად არის ის, რაც მე იმას ნიშნავდა, არ არსებობს. ასე რომ, Jay გაუმართლა ორივე ჯერ. და მან ასევე მიიღო გაუმართლა, რომ ბოლო წელს, მე უბრძანა ზოგიერთი Blu-ray დისკებზე რეალურად გასცემენ. მე ვწუხვარ, ამ წელს, არ აქვს იგივე, ტრევორ. მაგრამ უკეთესი ჯერ კიდევ რამდენიმე წლის უკან. და ზოგიერთი მოგეხსენებათ, ამ თანამემამულე, შონ, რომელიც, როცა ის CS50, ეჭვქვეშ ზუსტი იგივე პრობლემა, თუმცა SD, როგორც თქვენ მალე ვხედავ, უკან დღეში. თქვენ ნახავთ, რომ არათუ მან ცოტა უფრო მეტია, ვიდრე Jay, პატარა უმეტეს Trevor, ეს იყო რეალურად ეს მშვენიერი შესაძლებლობა ჩაერთონ თითქმის ყველას გულშემატკივარი la ფასი არის სწორი, რაც ხელს უწყობს მას იპოვოს ნომერი ჩვენ ეძებს. მოდით. მიიღოს სწრაფი შევხედოთ. [ვიდეო აღწარმოების] -OK. ასე რომ, თქვენი ამოცანაა, აქ, Sean, შემდეგ. მე არ იმალება უკან ამ კარები ნომერი შვიდი. მაგრამ მოახერხა მოშორებით ზოგიერთი კარები ასევე არიან სხვა უარყოფითი რიცხვები. და თქვენი მიზანია ვფიქრობ ამ ყველაზე გრაფაში ნომრები მხოლოდ მასივი, ან უბრალოდ თანმიმდევრობა ცალი ქაღალდი ნომრები მათ უკან. და თქვენი მიზანია, მხოლოდ გამოყენებით დაბრუნება მასივი აქ, იპოვეთ ჩემთვის ნომერი შვიდი. და ჩვენ შემდეგ ვაპირებთ კრიტიკა, როგორ წავიდეთ შესახებ ვაკეთებთ. -ყველა უფლება. მოძებნა us ნომერი შვიდი, გთხოვთ. No. ხუთი, 19, 13. [იცინის] ეს არ შეასრულა კითხვაზე. ერთ-ერთი. [იცინის] ამ ეტაპზე, თქვენი ანგარიში არ არის ძალიან კარგი, ასე რომ თქვენ შეიძლება ასევე შენარჩუნება აპირებს. სამი. [იცინის] ტურიზმი. სიმართლე გითხრათ, მე ვერ დაეხმარება, მაგრამ საინტერესოა, რა თქვენ კი ფიქრი, ისე [იცინის] მხოლოდ ყველაზე ზედიზედ, ასე რომ თქვენ მოხვდით სამი მარცხენა. ასე რომ, ჩემთვის შვიდი. [იცინის] 17. შვიდი. [ტაში] ყველა უფლება. [END აღწარმოების] დევიდ ჯ Malan: ასე რომ, ჩვენ შეგვიძლია უყურებს ამ მთელი დღის განმავლობაში. და რა თქმა უნდა, ზოგიერთი წლევანდელი demos ალბათ ახლა დასრულდება up შემდეგი წლის ვიდეო ისევე. ასე რომ, ახლა მოდით რეალურად ფოკუსირება ალგორითმები აქ, და თუ ჩვენ არ შეგვიძლია ახლა დაიწყება გააფორმოს როგორ შეგვიძლია წავიდეთ მისაღებად ჩვენი მონაცემებით ამ აცხადებენ, რომ ეს დახარისხებული, ასე რომ, საბოლოო ჯამში, ჩვენ შეგვიძლია რეალურად ძებნის უფრო ეფექტურად. და მიუხედავად იმისა, რომ ჩვენ ვაპირებთ გამოიყენოთ საკმაოდ მცირე მონაცემები კომპლექტი, მოსწონს რვა ნომერს ჩვენ აქ ფორუმში, საბოლოო ჯამში, ეს იგივე იდეები შეიძლება მიმართოს 1,000 საშუალებებით, მილიონი საშუალებებით, 4 მილიარდი საშუალებებით, რადგან ალგორითმები ვაპირებთ, რომ ფუნდამენტურად იგივე. ასე რომ, ეს არის ჩვენი ბოლო შესაძლებლობა მოხალისეები დღეს, მაგრამ ალბათ ყველაზე ჩართული ერთი, რისთვისაც აუცილებელია რვა მოხალისეები ამუშავება და ფეხით ჩვენს მეშვეობით პროცესი დახარისხება რა მალე იქნება ეს მუსიკა დგას აქ. დავიწყებ უკან აქ. ასე რომ, ერთი turquoise-- მწვანე არის ეს? თქვენ ჩადენილი? ორი. კარგით ქვემოთ. OK. სამი. ოთხი. ნება მომეცით OK, ხუთ. თქვენ მიმდინარეობს მიერ წარდგენილი თქვენი მეგობარი. ექვსი, შვიდი, რვა. კარგით up. ყველა უფლება. დიდი მადლობა. კარგით up. კარგით up. ყველა უფლება. რა გვაქვს აქ და ეს შორის უფრო უხერხულ პირობა, მას შემდეგ, რაც ეს მოითხოვს, რომ თქვენ იუმორის მე უბრალოდ ცოტა დრო. თქვენ უნდა იყოს ნომერ პირველი. რა გქვია? ანანი: ანანმა. დევიდ ჯ Malan: ანანმა. დავით. რა გქვია? JOSEPH: Joseph. დევიდ ჯ Malan: იოსები, თქვენ ხართ ნომერი ორი. SERENA: Serena, ნომერი სამი. შტეფან, ნომერი ოთხი. CYNTHIA: Cynthia. დევიდ ჯ Malan: Cynthia, ნომერი ხუთი. [INAUDIBLE] დევიდ ჯ Malan: [INAUDIBLE]. დავით, ნომერი ექვსი. MATT: Matt. დევიდ ჯ Malan: Matt ნომერი შვიდი. და? WAVERLY: Waverly. დევიდ ჯ Malan: Waverly, ნომერი რვა. ყველა უფლება. თუ შეიძლება whoops. თუ თქვენ, როგორც თქვენი პირველი გამოწვევა, არსებობს რვა მუსიკა სადგამები აქ წინაშე აუდიტორიას. თუ თქვენ ვერ დააყენა თქვენი ნომრები ეს მუსიკა დგას ისე, რომ ისინი გამოდიან იგივე ნომრები ფორუმში. ასე რომ მიიღოს თქუენგან ჰგავს, რომ აყენებს თქვენი ნომრები ამ მუსიკა დგას აქ. შესანიშნავი ჯერჯერობით. შესანიშნავი. OK. ასე რომ, ახლა ჩვენ ვაპირებთ, ვთხოვოთ კითხვა: რამდენიმე სხვადასხვა გზა. როგორ შეგვიძლია წავიდეთ შესახებ დახარისხება ეგ აქ? იმის გამო, რომ ჩვენ გვქონდა რამდენიმე მიდგომები ადრე, რომლის დროსაც ჩვენ სახის მიღების ორი სხვადასხვა თაიგულების. და მაშინ ჩვენ, ზოგადად, piecing რამ ერთად. როგორც კი დაინახა ორი ნომრები რომ ეკუთვნოდა ერთად, ჩვენ მათ ერთად. ორი ასო, რომელიც ეკუთვნის ერთად. მაგრამ ვნახოთ, თუ ჩვენ ვერ გააფორმოს ეს, ასე, რომ ჩვენ საბოლოოდ უნდა ზოგიერთი ფსევდო კოდი თქვენ, , რომელიც შეგიძლიათ ამ პრობლემების მოგვარებას. ასე რომ, ახლა ვეძებ out ამ ნომრები აქ. და მე ვხედავ მთელი bunch of შეცდომები. საბოლოო ჯამში, მინდა ერთი მარცხენა და რვა უფლება. ასე რომ, მე ვუყურებ ეს ორი, ოთხი და ორი. და რა პრობლემაა, ბუნებრივია? ჰო. ასე რომ. ორი აშკარად მოდის ადრე ოთხი, ასე რომ თქვენ იცით, რა? ნება მომეცით პირველი მიიღოს ხარბ მიდგომა, თუ თქვენ, ისევე, როგორც პრობლემა მითითებული one-- თუ გავიხსენებთ საწყისი სტანდარტული გამოცემა პრობლემა კომპლექტი ერთი, სადაც მე მხოლოდ ადგილობრივად პრობლემის მოგვარება ეს არის აქ ჩემს წინ და ვხედავ, სადაც ეს გამახსენა. OK. ასე რომ, ორი და ოთხი, ნება მომეცით წავიდეთ წინ და მხოლოდ სვოპ ორი. თუ შეგიძლიათ გადაადგილება ფიზიკურად საკუთარი თავი და თქვენი ქაღალდი, მე, როგორც ჩანს მიღებული მიუთითეთ უკეთესი სახელმწიფო. ახლა, ისინი კარგი. მე ვაპირებ გადაადგილება, ოთხი და ექვსი, კარგად გამოიყურება. არ არის პრობლემა. ექვსი და რვა, OK. რვა და ერთი, კიდევ ერთი პრობლემა. იმის გამო, რა არის ნამდვილი დაახლოებით რვა და ერთი? ერთ-ერთი საქმე, სანამ რვა, და ასე რა უნდა გავაკეთოთ? მოდით სვოპ ამ ორი. ერთი და რვა. და ახლა, მე ვაპირებ შენარჩუნება აპირებს. მე ვაპირებ შენარჩუნება ეძებს წინ. და ვნახოთ, რა მოხდება. რვა და სამი, ერთი რა თქმა უნდა, მწყობრიდან. მოდით გაცვლა. რვა და შვიდი, რა თქმა უნდა. მწყობრიდან. მოდით გაცვლა. რვა და ხუთი, რა თქმა უნდა, მოდით გაცვლა. ყველა უფლება. სია დალაგებულია. დიახ? დიახ, ცხადია, არა. მაგრამ ეს ცოტა უკეთესი, არა? იმის გამო, რომ გაფრთხილების რა მოხდა. ყოველ დროს, ჩვენ შესრულებული swap, პატარა ნომერი სახის percolated, რომ გზა, და უფრო დიდი რაოდენობის percolated ამ გზით, და ჩვენ გამოგიგზავნით დაიწყოს განაცხადა bubbled რომ მარცხენა ან bubbled უფლება. ახლა, ეს არ არის საკმარისი, იმიტომ, რომ საუკეთესო რიგი შეიძლება არ გადავიდა ერთ ადგილზე წინ, ან უარეს შემთხვევაში, რიგი შეიძლება ჰქონდეს გადავიდა ერთ ადგილზე შემდგომი. ასე, რომ თქვენ იცით, რა, ამ სახის მუშაობდა კარგად ჯერჯერობით. ნება მომეცით, უბრალოდ ცდილობენ კიდევ ერთხელ. ორი და ოთხი, ისინი OK. ოთხი და ექვსი, ისინი OK. ექვსი და ერთი, მწყობრიდან. მოდით სვოპ ორი. ახლა კი, შეამჩნია პრობლემის დაწყებული მისაღებად ცოტა უკეთესი ერთხელ. ექვსი და სამი, მწყობრიდან. მოდით სვოპ ორი. ექვსი და შვიდი, თქვენ კარგი. შვიდი და ხუთი, რა თქმა უნდა, მწყობრიდან. შვიდი და რვა, რათა. და ახლა, მე ალბათ უნდა ამისათვის რამდენიმე ჯერ. და სინამდვილეში, ვფიქრობ, რომ საკუთარი თავი ალბათ, თუ რამდენჯერ მაქსიმალურად შეიძლება მე უნდა ვიაროთ წინ და უკან? ჩვენ დავბრუნდებით რომ. ასე რომ, ორი და ოთხი კვლავ OK. ოთხი და ერთი, nope. ასე რომ, მოდით გაცვლა. ისევ და ისევ, შეამჩნია ვიზუალურად ერთი სახის bubbling მარცხნივ, სადაც უნდა იყოს. ოთხი და სამი გაცვლა. ოთხი და ექვსი. ექვსი და ხუთი გაცვლა. ექვსი და შვიდი. შვიდი და რვა კარგი. კარგი. ჩვენ ვიღებთ კიდევ უკეთესი. ასე რომ, ვნახოთ. ამჟამად, ჩვენ გვაქვს ორი და ერთი. რა თქმა უნდა, სვოპ. ორი და სამი, სამი და ოთხი, ოთხი და ხუთი, ექვსი და შვიდი, შვიდი და რვა. კარგი. და იცით რა? იმის გამო, რომ მე ერთი ცვლილება არსებობს, ნება მომეცით ამის ერთ-ერთი საღი აზრის ქვითარი. ნება მომეცით წავიდეთ ყველა გზა დაბრუნება დასაწყისში. OK. ერთი, ორი yup, ხედავთ? რაღაც არასწორია. სამი, ოთხი, ხუთი, ექვსი, შვიდი, რვა. და ამ ბოლო პასი, რომლებიც თქვენ კომფორტულად ჩემი ახლა ამტკიცებენ, რომ ეს არის გადანაწილებული? OK. ვიზუალურად, რომ აბსოლუტურად მართალია. მაგრამ ფუნქციურად, რა ისიც მხოლოდ მოხდეს ამ ბოლო პასი, რომელიც საშუალებას გაძლევთ იმის დასადასტურებლად, რომ ეს სია მართლაც გადანაწილებული? რა გავაკეთო თუ არა ამის გაკეთება ბოლო უღელტეხილზე? აუდიტორია: არ იყო ცვლილებები. დევიდ ჯ Malan: უკაცრავად? აუდიტორია: ცვლილებები. დევიდ ჯ Malan: არ იყო ცვლილებები. ასე რომ, ეს იქნება სულელური ჩემთვის გავაკეთოთ, რომ იგივე ალგორითმი ერთხელ თუ მე არ გაუკეთებია ცვლის პირველად. და სახელმწიფო არ შეცვლილა. რა თქმა უნდა, მე არ ვაპირებ, რომ ნებისმიერი ცვლის მეორედ. ასე რომ, ეს არ ემუქრება უნდა ვთქვა, სია დალაგებულია. და მართლაც, ეს არის ის, რომ ჩვენ ზოგადად დარეკეთ bubble sort, რომლის pairwise, თქვენ შეცდომების გამოსწორების კიდევ ერთხელ, და ისევ და ისევ, და თქვენ შენარჩუნებას აპირებს უკან და მეოთხე, და უკან და მეოთხე, სანამ რათა არსებობს ასეთი გაცვლებს, სადაც წერტილი თქვენ შეუძლია იყოს დარწმუნებული, ჰო, მე დასრულდა აფიქსირებს ყველა შეცდომები. მოდით აღადგინოთ და ცდილობენ სხვა მიდგომა. თუ თქვენ ბიჭები დაბრუნდეს შევიდა იმისათვის, რომ თქვენ იყო მომენტში წინ, რაც ჩანდა მოსწონს ეს. ახლა, მოდით მიიღოს მიდგომა ცოტა უფრო გამოცდა წიგნი, რომლის დროსაც ჩვენ მუდმივად შერჩევის წერილი ანბანი რომ ჩვენ სახის სურდა გამკლავება მომავალი. შესაძლოა, ეს იყო მაღალი წერილი, როგორიცაა, ან დაბალი წერილი ზ ასე რომ ყველას უკან ამ მიზნით. ახლა კი ნება მომეცით ამის გაკეთება. ვნახოთ, მე ვიცი, მე რვა ნომერს აქ. მე ვაპირებ წავიდეთ წინ და უბრალოდ შეგნებულად აირჩიეთ პატარა ელემენტებს. მარჯვენა? ეს, როგორც ჩანს, ინტუიციური ძალიან. რატომ არ იპოვოს პატარა ელემენტს, ამას სადაც მას ეკუთვნის, ამის შემდეგ მიიღონ შემდეგი პატარა ელემენტს, დააყენა სადაც მას ეკუთვნის და მხოლოდ გავიმეორო. იმის გამო, რომ ინტუიციურად, რომ უნდა ვიმუშაოთ ძალიან. ასე რომ ოთხი, რომ საკმაოდ მცირე რაოდენობით. მე ვაპირებ მახსოვს, სადაც ეს არის. ერთი წუთით. ორი პატარა. ნება მიბოძეთ ახლა მახსოვს, სადაც ორი არის, და დაივიწყოს ოთხ. ჩვენ გაუმკლავდეთ მოგვიანებით. ექვსი, მე არ ვარ დაინტერესებული. რვა, მე არ ვარ დაინტერესებული. ერთ-ერთი ჩემი ახალი მცირე რაოდენობით. ამიტომ, მე ვაპირებ უნდა გვახსოვდეს, სადაც არის. სამი, არ არის დაინტერესებული. Seven, არ არის დაინტერესებული. ხუთი, არ არის დაინტერესებული. ასე რომ, გარეშე დაცემით off სცენაზე წელს, მე ვაპირებ დაიბრუნოს ნომერი one-- და რა იყო თქვენი სახელით კიდევ ერთხელ? ანანი: ანანმა. დევიდ ჯ Malan: ანანმა. და თუ შეიძლება შეუერთდეს me at დასაწყისში სია, მოდით ვთქვათ, სადაც თქვენ ეკუთვნის. Unfortunately-- რა გქვია? STEFAN: Stefan. დევიდ ჯ Malan: შტეფან გზა. ასე რომ, სანამ შტეფან წყვეტს ამ პრობლემა, რა უნდა გავაკეთოთ? რას ვაკეთებთ შტეფან? აუდიტორია: [INAUDIBLE]. დევიდ ჯ Malan: OK. ასე რომ ჩვენ შეგვიძლია ამის გაკეთება. ჩვენ შეგვიძლია ერთგვარი მიიღოს შტეფან და მისი ოთხი, და მხოლოდ დააყენა ეს ცვლადი და ჩატარების შესახებ, რომელიც მას გარკვეული დროის, რითაც ოთახი ნომერ პირველი. და ეს არ არის ცუდი. მე შეიძლება ვივარაუდოთ, რატომ არ ჩვენ უბრალოდ შტეფან აქ? რატომ შეიძლება ეს არღვევს ერთი იდეები, ჩვენ დავიწყეთ ლაპარაკი ბოლო დროს, გასულ კვირას? ჰო? აუდიტორია: [INAUDIBLE]. დევიდ ჯ Malan: არ არსებობს ინდექსი იგი. თუ ფიქრობთ, რომ ეს, მართლაც, როგორც მასივი, ეს არის, როგორც უარყოფითი, ასე რომ არ არსებობს მეხსიერება რეალურად აქ, თუ ეს მართლაც მასივი, როგორც ჩვენ განაცხადა გასულ კვირას ლექცია. ასე რომ, ჩვენ არ უნდა გავაკეთოთ ეს. ჩვენ შეიძლება ჩაწეროთ იგი ცვლადი. ან იცით რა? გავიგე, ვინმე ვარაუდობენ, რომ ეს. რა უნდა გვექნა შტეფან? რატომ არ გვაქვს მხოლოდ გამოსახლება მას და ამით მას მეტი, სადაც ნომერ იყო. ასე რომ, თუ გსურთ წავიდეთ იქ. და მართლაც, ეს არის საკმაოდ კარგი გამოსავალი. ახლა, ერთი მხრივ, მე სახის გააკეთა პრობლემა გაუარესდა. ოთხი არის შორს საიდანაც უნდა იყოს. ეს უნდა იყოს ამ მიმართულებით ნახევარი. მაგრამ იცით რა? რომ ყოფილიყო ცუდი წარმატებას. იქნებ ნომერი რვა აქ იყო. ასე რომ, შესაძლოა, ჩვენ გვინდა მიღებული გაუმართლა, და მივიღებთ რვა დაახლოება ბოლოს. ასე რომ, დღის ბოლოს, ეს სახის ყველა საშუალოდ. ჩვენ არ უნდა ზრუნავდეს ოთხ. ყველა მე აინტერესებს ახლავე შერჩევის პატარა ელემენტს. ახლა კი, რა მე ვაპირებ გავაკეთოთ არის დაივიწყოს ნომერ მუდმივად, იმიტომ, რომ მე ვიცი, სიაში ჩემს უკან არის გადანაწილებული. ასე რომ, ჩემი სია ადრე ზომის რვა. ახლა, ეს ზომა შვიდი. ასე რომ, ჩემი პრობლემა დღითიდღე პატარა, თუმცა ხაზოვანი. ასე რომ, ახლა მე ვაპირებ აირჩიეთ დღევანდელი პატარა ელემენტს, ორი. ექვსი, რვა, ოთხი, სამი, შვიდი, ხუთი. ეს იყო პატარა ელემენტს. ასე რომ, რა ვარ მე გაკეთებას აპირებს with-- რა იყო თქვენი სახელით კიდევ ერთხელ? JOSEPH: Joseph. დევიდ ჯ Malan: ჯოზეფ? ჩვენ ვაპირებთ, რომ დატოვოს ჯოზეფ ადგილზე. ახლა, მე ვაპირებ პრეტენზია რომ ეს ბიჭები are-- კარგად, მე ვიცი, რომ ეს ორი უკვე დახარისხებული. მოდით ახლა ფოკუსირება დარჩენილი სიაში. ექვსი მიმდინარე პატარა. რვა მეტია. ოთხი არის დღევანდელი პატარა. სამი არის დღევანდელი პატარა. და ახლა, მე ვაპირებ აირჩიოთ სამი, რომელიც is-- რა არის შენი სახელი ისევ? SERENA: Serena. დევიდ ჯ Malan: Serena, თუ შეიძლება Grab თქვენი ნომერი და swap with-- KALSANG: Kalsang. დევიდ ჯ Malan: Kalsang. კარგით უკან, და ჩვენ აპირებს სვოპ ორი. და ახლა, მოდით დააყენა ამ ავტოპილოტი. მე ვაპირებ წასვლა და დატოვოს ის, რომ თქვენ ბიჭები აირჩიოთ შემდეგი პატარა ელემენტებს. Dun, Dun, Dun, Dun. პუნქტების ოთხი, რა უნდა გავაკეთოთ? შესანიშნავი. ახლა, მე ვაპირებ, რათა კიდევ ერთი აკეთებს. Dun, Dun, Dun, Dun. მე ვხედავ ხუთ შემდეგი ყველაზე პატარა. ახლა, მე ვაპირებ მიიღოს სხვა აკეთებს. Dun, Dun, Dun, Dun. ექვსი ყველაზე პატარა. კარგი. შვიდი პატარა. ცვლილება არ არის. რვა არის პატარა. შესრულებულია. ასე რომ, რაც ჩვენ უბრალოდ გაკეთდეს iteratively შერჩევის ერთ-ერთი ელემენტია შემდეგ სხვა არის განახორციელოს, რასაც ჩვენ ძალიან აპირებს გააფორმოს, როგორც შერჩევა ერთგვარი. და ეს ალბათ კი მარტივი ასახსნელია, რომ ფაქტიურად ყველა თქვენ გსურთ გააკეთოთ უბრალოდ შეინახოს ბრუნდება და მეოთხე მეშვეობით სიაში შერჩევის, მომდევნო პატარა ელემენტის, სანამ თქვენ გაკეთდეს. ასე რომ, ეს კი მარტივი, ალბათ ინტუიციურად, ვიდრე ბოლო. მოდით ცდილობენ ერთი ბოლო. თუ თქვენ ბიჭები აღადგინოთ საკუთარი თავი შევიდა შემდეგ თანამდებობებზე ერთი საბოლოო დრო, ვნახოთ, თუ ჩვენ არ შეგვიძლია ახლა formalize ერთი სხვა მიდგომა. ფაქტობრივად, ვინმე იქ მინდა შესთავაზოს როგორ სხვაგან ჩვენ შეიძლება წავიდეთ შესახებ ამით? გარეშე არიგებდა buzzwords ან სახის პასუხი, რომ უკვე ცნობილია, უბრალოდ ინტუიციურად, თუ რა უნდა გვექნა? აუდიტორია: [INAUDIBLE]. დევიდ ჯ Malan: ჰო. ასე რომ ზოგიერთი დიდი ინტუიცია არსებობს. კარგი რამ ჩანს, ხდება დღემდე კომპიუტერულ მეცნიერებაში, როდესაც ჩვენ გაყოფა და დაიპყროთ პრობლემა გამყოფი ის ნახევარზე და ნახევარი და ნახევარი. ასე რომ, რა თქმა უნდა, ჩვენ შეიძლება დაიწყოს, რომ. და ის ფაქტი, რომ იქნება, ჩვენ ხედავთ, ჩვენი ერთ-ერთი საუკეთესო გადაწყვეტილებები ამჟამად. მაგრამ მოდით, დაუბრუნდეს, რომ ხანგრძლივი. ფაქტობრივად, ჩვენ ვაპირებთ, რომ რომ ცოტა მოგვიანებით ამ კვირაში. რა შეიძლება გავაკეთოთ, რომ მოსაგვარებლად? ასე რომ ყველას აქ არის ერთი შეხედვით შემთხვევითი მიზნით. იცით რა? იმის ნაცვლად, უკან და მეოთხე, უკან და მეოთხე, უკან და მეოთხე ყოველ ჯერზე, ეს იგრძნობა მე ვაკეთებ ბევრი ფეხით. რატომ არ მხოლოდ იწყება დასაწყისში სია, და მხოლოდ ბოლო ოთხი, სადაც მას ეკუთვნის? ნება მომეცით, დავუშვათ მომენტში, რომ ჩემს სიაში მხოლოდ ამ პირველ ელემენტს. ოთხი დახარისხებული ამ მომენტში, თუ ყველა მე აინტერესებს ყველაფერი აქ? ეს არის ერთგვარი trivially ასეა, არა? მსგავსად სია, რომელიც შეიცავს ერთი ნომერი, და რომ ნომერი ოთხი აშკარად გადანაწილებული. ნება მომეცით, უბრალოდ ითვალისწინებს რომ ეს სია დალაგებულია. მაგრამ ახლა მე მაქვს დანარჩენი ამ სიაში. ასე რომ, ახლა მე ექმნებათ ორი. სად ორი აშკარად ეკუთვნის მიმართებაში ოთხი? სანამ ოთხი. ასე რომ, რა გავაკეთო აქ? რა არის შენი სახელი ისევ? JOSEPH: Joseph. დევიდ ჯ Malan: იოსები, თუ შეიძლება უკან დახევას მხოლოდ ერთი წუთით თქვენი ნომერი. და ახლა რა უნდა შტეფან აქ? მოდით გადაიტანოს შტეფან მეტი აქ. და ახლა, მოდით ჯოზეფ მოდის აქ. და ახლა, ნება მომეცით აცხადებენ, რომ აქ ყველაფერი დალაგებულია. ასე რომ, მსგავსი შედეგი, მაგრამ ფუნდამენტურად განსხვავებული მიდგომა. მე კი არ ჩანდა, რაც დახვდა. მე უბრალოდ შეინახოს აღების ელემენტები როგორც ისინი გადასცა ჩემთვის, და მათთან გამკლავება. ასე რომ, ახლა მე ვხედავ ნომერი ექვსი. სად ნომერი ექვსი ეკუთვნის? ჩვენ გვაქვს ორი, ოთხი, ექვსი. სწორედ იქ, სადაც ის არის ახლა. მოდით დატოვება, რომ მარტო, და ახლა ამტკიცებენ, რომ ეს ნაწილი სიაში არის გადანაწილებული. ასე რომ, ეს გრძნობს ფუნდამენტურად განსხვავებული, რომ მე მხოლოდ მოძრავი მეშვეობით სიაში აქ ხაზოვანი და მე არასოდეს გაორმაგდა უკან. დიახ. ყველა უფლება. ასე რომ, რვა, სადაც ხარ? სწორედ აქ. სრულყოფილი. ახლა, ერთი. Uh-oh. ეს იგრძნობა ეს იქნება ძვირი. ახლა, წინა ალგორითმი, მე უბრალოდ გაცვალეს ადამიანი. ასე რომ, მე, შესაძლოა, მას ყველა გზა დასაწყისში, მაგრამ შემდეგ გადავიდა იოსები. მაგრამ თუ მე გადაადგილება ჯოზეფ, ახლა რა იქნება არასწორი? ახლა, მე ერთგვარი undone-- მე მიღებული ერთი წინ გადადგმული ნაბიჯია და შემდეგ ერთი ნაბიჯი უკან, რადგან ახლა ჯოზეფ იქნება მწყობრიდან. ასე რომ, მოდით ეს. თუ თქვენ ვერ მიიღოს ნომერ და უკან დახევას რაღაც მომენტში. როგორ შეგვიძლია put-- რა იყო თქვენი სახელით კიდევ ერთხელ? ანანი: ანანმა. დევიდ ჯ Malan: ანანის ადგილი? რა უნდა მოხდეს რუსეთთან მიმართებაში ორი, ოთხი, ექვსი, რვა? ისინი ყველა უნდა გადაიტანოს. ასე რომ, თუ რვა მინდა გადაიტანოს პირველი, მაშინ ექვსი, მაშინ ოთხი, შემდეგ ორი. და მაშინ ანანი, თუ მინდა მინდა მოსვლა აქ, კარგი. მაგრამ აქ, ჩვენ მხოლოდ სახის გადახდილი ფასი სხვადასხვა წერტილი ალგორითმი. ვინაიდან ბოლო დროს შერჩევა დალაგების, და კიდევ bubble sort, მე ფეხით უკან და მეოთხე, უკან და მეოთხე, რომელიც რა თქმა უნდა დასძინა მდე დროის ბრძენი, და ფაქტიურად ეტაპობრივად. Insertion დალაგების, პირველ რიგში, ერთი შეხედვით, ჰგავს ეს სუპერ ჭკვიანია, რომ მე მხოლოდ მიღების ნელი, დამატებითი პროგრესის, მაგრამ მე არ ვაპირებ ამ უკან და მეოთხე. მაგრამ თუ ვინმე მართლაც მწყობრიდან, ცნობა ყველა ნაწარმოების მე მქონდა უნდა გააკეთოს. მე უნდა გადავიდეს ნახევარში სია უბრალოდ, რათა ოთახი ნომერ პირველი. ასე რომ, ეს იგივე თანხა სამუშაო დღემდე ეს გრძნობს, უბრალოდ სხვადასხვა ტიპის მუშაობა. მოდით, გავაგრძელოთ. ახლა ჩვენ ვიცით, რომ ყველას ერთიდან რვა დახარისხებული. აქ, მე მაქვს ნომერი სამი. თუ გსურთ შეარჩიო ნომერი სამი, უკან დახევას ერთი. და რა ბიჭები უნდა გავაკეთოთ? Yep. ასე რომ, კიდევ ერთი, ორი, სამი ნაბიჯი. სამი ერთეული დრო, რომ მხოლოდ ეღირება ჩემთვის, ისე, რომ სამი შეიძლება ახლა შეესაბამება. და ბოლოს, შვიდი. მოდით წავიდეთ წინ და თქვენ მიიღოს უკან გადადგმული ნაბიჯია. ეს არის მხოლოდ აპირებს ეღირება us ერთი ერთეული დრო, მაგრამ რომ კარგადაა. და ახლა, ხუთი აპირებს იყოს ცოტა უფრო ძვირი. თუ გსურთ, რომ უკან დახევას. ჩვენ უნდა გადავიდეს რვა, და შვიდი და ექვსი. და მაშინ ყველას არის გადანაწილებული. ასე რომ, დიდი ხელი ჩვენი მოხალისეები აქ. დიდი მადლობა. [ტაში] დიდი მადლობა. დიდი მადლობა. მოდით ვნახოთ, ახლა, თუ რამდენად ძვირადღირებული ყველა რომ იყო. მოდით, განვიხილოთ, ალბათ, უმარტივესი ამ, bubble sort. და მე ვიტყვი, მარტივი, მხოლოდ იმიტომ, რომ თქვენ შეგიძლიათ გადაწყვიტოს იგი ხარბად მხოლოდ დაფიქსირება ბიტოპოლოგიური პრობლემა აქ. ფიქსის ბიტოპოლოგიური პრობლემა აქ, ისევ და ისევ და ისევ იმეორებს, როგორც ბევრი ჯერ, როგორც თქვენ ნამდვილად უნდა. გამოდის, რომ ერთად bubble sort, ასევე, რამდენი ნაბიჯები მე უნდა მიიღოს პირველი უღელტეხილზე რომ ალგორითმი? მე შეიძლება take-- მოდით see-- ერთი, ორი, სამი, ოთხი, ხუთი, ექვსი, შვიდი. და იქ რვა ელემენტებს აქ. ასე რომ, ო მინუს 1 ნაბიჯები, რათა მიიღონ დასაწყისში სიაში ბოლომდე სიაში. მაგრამ შერჩევის დალაგების, გავიხსენოთ, რომ მე ვარ შერჩევის ელემენტები ისევ და ისევ და ისევ, ეს არის პატარა, მე აყენებს ის ადგილი, მაგრამ მაშინ მე არ ვარ ეძებს ჩემს უკან კიდევ ერთხელ. ასე რომ, მე ვფიქრობ, რომ ეს უფრო ნათელი შემდეგ, რომ პირველად, მე შეიძლება უნდა მიიღოს ყველა ო მინუს 1 ნაბიჯები იპოვოს პატარა ელემენტს. მერე დააყენა მათ ადგილზე, და მე გამოსახლება ვინც იყო აქ ადრე. მაგრამ მაშინ მე არ უნდა შენარჩუნება ეძებს ამ ელემენტის, იმიტომ, რომ მე ვიცი, რომ ეს უკვე პატარა. ასე რომ, ახლა შემიძლია შევხედოთ მხოლოდ შვიდი ელემენტები, მაშინ ექვსი ელემენტები, ხუთ ელემენტები, მაშინ ოთხი ელემენტები. ასე რომ, მათემატიკურად, თუ ო რიგი ელემენტები და ციფრები რომ ჩვენ დავიწყეთ, თქვენ წარმოიდგინეთ, რომ ეს არის იგივე, რაც n მინუს 1, პლუს N -2 ნაბიჯები, პლუს n მინუს 3 ნაბიჯები, პლუს n მინუს 4 ნაბიჯი, ყველა გზა ქვემოთ მხოლოდ ერთი ნაბიჯი. და მე ჩემს ბოლო პირი. და თუ გავიხსენებთ, რომ ბევრი საქართველოს სტატისტიკის წიგნები და მათემატიკის წიგნი აქვს იმ ფორმულები hardcover წინა ან უკანა მათ, გამოდის, რომ ამ სერიის შეიძლება გამოიხატოს უფრო მარტივად როგორც N ჯერ N მინუს 1 2. და ეს ჯარიმა, თუ ეს არ არის ბერკეტები თქვენი გონება. მაგრამ ეს მართლაც ასეა. ეს უბრალოდ მარტივი გზა წერის იგი. და მაშინ, თუ თქვენ ფიქრობთ უკან კლასის სკოლის როდესაც თქვენ უბრალოდ დავიწყებთ გამრავლებით ნივთების, ეს, რა თქმა უნდა, მხოლოდ n კვადრატში ო იყოფა 2. ყველა მე ვაკეთებ გაფართოება გამონათქვამები არსებობს. და მოდით ეს გადავწერო ცოტა განსხვავებულად. ეს n კვადრატი გაყოფილი 2 მინუს N / 2. ასე რომ კიდევ ერთხელ, მე უბრალოდ სახის გამოყენების ზოგიერთი არითმეტიკული მართავს იქ. მაგრამ შეამჩნია, ახლა, რომ ყველაზე დიდი ვადით ამ გამოხატვის, ასე ვთქვათ, ის არის, რომ n კვადრატში. ასე რომ, დიახ, ეს n კვადრატში გაყოფილი 2, მინუს N / 2. მაგრამ ზოგადად, თუ n იქნება დიდი მნიშვნელობა, მე ვაპირებ აცხადებენ, რომ n კვადრატში იქნება დომინანტური ფაქტორია. ეს იქნება დიდი წვლილი რაოდენობის ნაბიჯები, ვიდრე n / 2. ასე რომ, რას ნიშნავს ეს? მოდით ცდილობენ მარტივი მაგალითია, თუნდაც მიუხედავად იმისა, რომ მათემატიკის იღებს ცოტა დიდი. ასე რომ, დავუშვათ, რომ ჩვენ გვქონდა 1 მილიონი ადამიანი სცენაზე, და 1 მილიონი რამ ჩვენ გვინდა, რომ დასალაგებლად. მოდით plug მილიონი შევიდა ზუსტად, რომ ფორმულა იმისათვის, რომ ნახოთ რამდენი ნაბიჯები იგი იღებს სულ დასალაგებლად მილიონი ელემენტების გამოყენებით ვთქვათ, შერჩევა ერთგვარი. ასე რომ, ჩვენ გვექნება იგივე ფორმულა, როგორც ადრე. მე შეაერთედ მილიონი, ასე, რომ მე მილიონი კვადრატი გაყოფილი 2, მინუს მილიონი გაყოფილი 2. თუ რომ მათემატიკის წინასწარ აქ, ჩვენ გვაქვს 500 მილიარდი მინუს 500,000, რომელიც გვაძლევს 499.999.500.000, რომელიც საკმაოდ darn დიდი. სინამდვილეში, თუ შევადარებთ ახლა 499 მილიარდი, 999 მილიონი აშშ დოლარი, 500,000 წინააღმდეგ ჩვენი ორიგინალური ღირებულება, 500 მილიარდი, ეს ასე რა ახლოს. მარჯვენა? n კვადრატი გაყოფილი 2 აძლევს us-- უფრო სწორად, n კვადრატი გაყოფილი 2 მოგვცა 500 მილიარდი. ეს არის საკმაოდ darn ახლოს to 499.999.500.000, რაც უნდა ითქვას, გამოკლება off 500,000 ან უფრო ზოგადად, გამოკლება off N კვადრატში, ნამდვილად არ არის დიდი გარიგება. N კვადრატში რაც ამ ნომრები იზრდება ძალიან სწრაფად. ახლა, ეს არის მნიშვნელოვანი მხოლოდ იმ შემთხვევაში, როგორც ჩვენ, როგორც კომპიუტერული მეცნიერების, ზოგადად არ ვაპირებთ ზრუნვა იმდენად ნიუანსი ამ ფორმულები და ზუსტად რა ზუსტი პასუხი. ჩვენ ვზრუნავთ მხოლოდ, რომ თქვენ იცით, რა? ბოლოს დღეს, ეს ფორმულა არის ბრძანებით n კვადრატში. დიახ, ჩვენ ვყოფთ 2 არსებობს. დიახ, ჩვენ ვაკლებთ off n-2. თუმცა, დღის ბოლოს, ტერმინი რომ გტკივა ჩვენთვის და გვიჯდება ბევრი ნაბიჯები, რომ მოედანზე ვადით. ასე რომ, რა კომპიუტერის მეცნიერი აპირებს ზოგადად არის იგნორირება ყველა იმ პატარა წესრიგის თვალსაზრისით, და შევჩერდეთ ერთი, რომ ხელს უწყობს ყველაზე ღირებულება. და ეს კარგია, იმიტომ, რომ ჩვენ შეუძლია ახლა გაიგო ბევრად უფრო ზოგადი შესახებ ალგორითმები, და შეგიძლიათ შეადაროთ მათ. ხოლო ის ფაქტი, რომ მე ვარ გამოყენებით ამ O არის მიზანმიმართული. როდესაც ვამბობ ბრძანებით საქართველოს, მე კონკრეტულად გულისხმობდა რაღაც მოუწოდა დიდი ო და დიდი O არის ნოტაცია, რომ კომპიუტერი მეცნიერი აღსაწერად ზედა შეკრული რაღაც. ასე რომ, თუ ვიტყვით, რომ ალგორითმი არის დიდი O of n კვადრატში, როგორც მე შევთავაზე მხოლოდ მომენტში წინ, რომ საშუალება რომ ამ თვალსაზრისით მისი გაშვებული დრო და მისი ეფექტურობის, ის იღებს ბრძანებით N კვადრატში ნაბიჯები. იქნებ უფრო, იქნებ ნაკლები. მაგრამ ეს ბრძანებით n კვადრატში. და ეს არის ზედა ზღვარი. ეს არ იქნება უფრო მტკივნეული, ვიდრე. ეს არ იქნება N კუბი, ან 2 ო, ან რაღაც გაცილებით დიდია. ეს არის ზედა ზღვარი რაც არ უნდა, რომ ღირებულება. ასე რომ, თუ გავითვალისწინებთ, რომ, მოდით განვიხილოთ რამდენიმე მაგალითი. და ეს მხოლოდ სასრულ სია ძალიან საერთო გაშვებული ჯერ ამისთვის ალგორითმები, ნიშნავს, რომ საილუსტრაციო ზოგიერთი რამ, რომ ჩვენ ჩანს უკვე. ასე მაგალითად, იმ შემთხვევაში, შერჩევის დალაგების, რაც მე აცხადებდნენ აქ ის არის, რომ შერჩევის დალაგების გაშვებული დრო ბრძანებით n კვადრატში. უარეს შემთხვევაში, მე ვაპირებ აქვს მთელი bunch of შემთხვევითი ნომრები აქ. და როგორც ჩვენ ვნახეთ მათემატიკურად, თუ მე ივლით მეშვეობით სიაში მეშვეობით სია, შერჩევის შემდეგი ყველაზე პატარა ელემენტი ისევ და ისევ, თუ მე რეალურად დაწერეთ ყველა ნაბიჯები მე აღების, როგორც მე შევთავაზე formulaically ადრე, ეს ბრძანებით n კვადრატში ნაბიჯები, რომ მე აღების. და აღმოჩნდება, რომ ბუშტი დალაგება და Insertion დალაგების ისევე, როგორც ნელი უარეს შემთხვევაში. განვიხილოთ, მაგალითად, Insertion დალაგების, ძალიან ბოლო ალგორითმი ჩვენ განხილული, რაც ჰქონდა შევხედოთ ელემენტს, და შემდეგ ჩადეთ მას, სადაც მას ეკუთვნის. და მაშინ ჩვენ შევხედე შემდეგი ელემენტის, და შეიყვანეს, სადაც მას ეკუთვნის. ამიტომ მიგვაჩნია, რომ საუკეთესო სცენარი. დავუშვათ, რომ მე მქონდა ჩემი მოხალისეები გამოდიან ფაქტიურად, როგორც ეს, ერთი გზით რვა, უკვე გადანაწილებული. რამდენი ნაბიჯები არის Insertion დალაგების აპირებს დასალაგებლად რვა ადამიანი, იმ შემთხვევაში, თუ ისინი მიაღწევენ სცენაზე ეძებს მოსწონს ეს? რვა ადამიანი უკვე გადანაწილებული. და მე Insertion დალაგების. ეს ბოლო ალგორითმები. ისე, მოდით reenact რეალური სწრაფად. ასე რომ, თუ მე აქ იწყება ვხედავ. სად ერთი ეკუთვნის? ეკუთვნის უფლება აქ. მე ვხედავ ორი. სად ორი ეკუთვნის? სწორედ აქ. მე ვხედავ სამი. სად სამი ეკუთვნის? სწორედ აქ. მე ვხედავ ოთხ. სწორედ აქ. ხუთი, ექვსი, შვიდი, რვა. არ არსებობს მიზეზი, რომ გავიმეორებ. ასე რომ, რამდენი ნაბიჯები არის, რომ ამ თვალსაზრისით ო? ეს ბრძანებით n ნაბიჯები, არა? ო მინუს 1. მაგრამ მე წრფივი ნაბიჯები, და ახლა მე გაკეთდეს. ასე რომ, საუკეთესო შემთხვევაში, თუმცა. რაც შეეხება ცუდ შემთხვევაში? რა რვა იქ, და შვიდი ქვემოთ იქ, და ერთი და ორი აქ, ასე რომ რომ სიაში მართლაც შეცვალა? ისე, სინამდვილეში რა ხდება თუ ეს არის ნომერი? და ჩვენ ყველაფერს გავაკეთებთ, მხოლოდ რამდენიმე მაგალითი. რა მოხდება, თუ, რა თქმა უნდა, რვა აქ არის, და რიცხვი whoops. მერე რა, თუ, რა თქმა უნდა, ნომერი რვა არის ყველა გზა აქ, და მე გამოყენებით ჩანართი დალაგების? OK. I აცხადებენ, ამ ეტაპზე ეს არის ადგილი. მაგრამ ახლა, seven-- სადაც ჯერ შვიდი წავიდეთ? რა თქმა უნდა, მიდის აქ. ასე რომ, მე უნდა გადავიდეს რვა მეტი ერთ ადგილას. ახლა ექვსი, სად წავიდეს? ისე, ყველა უფლება. ახლა, მე უნდა გადავიდეს რვა მეტი ადგილი, და შვიდი მეტი ადგილი, და მერე ვეცემით ექვსი. ასე რომ, პირველად, ღირებულება მე ერთი ნაბიჯით დაფიქსირება რამ, მაშინ ღირს ჩემთვის ორი ნაბიჯი დაფიქსირება რამ. რამდენი ნაბიჯები არის ეს აპირებს დაფიქსირება რამ დააყენა ხუთ ადგილას? სამი. იმის გამო, რომ, ახლა მე მაქვს გადაადგილება ერთი, ორი, სამი. რამდენი ნაბიჯების იგი აპირებს იმისათვის, რომ ოთხი ადგილას? 4 + 5 + 6, პლიუს 7. ასე რომ, ეს მათემატიკურად იდენტურია ის, რაც ჩვენ აღწერილი შერჩევა ერთგვარი. ჩვენ გვყავს ამ სერიის ეს მხოლოდ გაზრდის. 1 + 2 + 3 + 4, ან პირიქით, 7 + 6 + 5 პლუს 4 დასძენს მდე დღევანდელი მიზნებისათვის, ბრძანებით n კვადრატში. ნება მომეცით, ითვალისწინებს, რომ ძალიან bubble sort ასევე n კვადრატში. იმის გამო, რომ bubble sort, თითოეული დროს მე გავლა სიაში, მე აღების დაახლოებით რამდენი ნაბიჯები? ყოველ ჯერზე მე ფაქტიურად ფეხით არ არსებობს? დაახლოებით ო ნაბიჯები. მაგრამ რამდენჯერ შეიძლება მე უნდა გაიაროს სიაში? ისე, უხეშად n დროს. იქნებ n მინუს 1, მაგრამ უხეშად N ჯერ. ისე, რატომ არის, რომ? ისე, bubble sort, თუ ჩვენ დავიწყებთ bubble sort, სია ყველაზე უარესი სიტუაცია, რომელიც ისევ სრულიად უკან, რა მოხდება? მე გავლა სიაში და ნომერი ერთი ეკუთვნის ყველა გზა იქ. მაგრამ bubble sort, თუ რამდენად შორს ჯერ ერთი გადაადგილება ჩემი პირველი გადის სიაში? რამდენი ლაქების მან მიიღოს ახლოს სწორი ადგილი? მხოლოდ ერთი. ასე რომ, თუ სახის მიზეზი ამ გზით, ყოველ დროს, ეს ალგორითმი, დავით აღების უხეშად N ნაბიჯები. მაგრამ რამდენი გადის მეშვეობით სიაში არის ის, აპირებს ერთი ბუშტი რომ მარცხნივ, სადაც მას ეკუთვნის? მან მიიღო გადაადგილება, როგორიცაა, n ფართები ამ გზით. ასე რომ მხოლოდ ამის დახარისხება სიაში, მაქვს ფეხით უკან და მეოთხე N ჯერ. და ყოველ ჯერზე, მე ვარ ეძებს n ელემენტებს. ასე რომ, n რამ ო ჯერ ბრძანებით n კვადრატში. ახლა, ჩვენ ვხედავთ ზოგიერთ შორტები რომ ჩართული CS50 შემდეგი პრობლემა მითითებული, მეორე მიდგომა ამ, მაგრამ ახლა, მოდით, უბრალოდ მიგვაჩნია ზოგიერთი სხვა გაშვებული ჯერ, მით უმეტეს, თუ დახარისხება პირობა მიიღოს ცოტა დრო ჩაძირვაში. რა არის ალგორითმი ჩვენ ვნახეთ უკვე რომ იღებს ბრძანებით N ნაბიჯები? რა უნდა მიიღოს წრფივი ნაბიჯები, რომლებიც ჩვენ ვნახეთ დღემდე? რა არის ეს? სატელეფონო ცნობარი ძებნა. პირველი ალგორითმი. მარჯვენა? სადაც ჩვენ ვართ ხაზოვანი ეძებს მაიკ სმიტი? მართლაც. კვირაში ნულოვანი, როცა დაიწყო გარდამტეხი ერთ გვერდზე დროს, და მე კი განაცხადა, რომ ეს იყო ერთგვარი წრფივი განცდა ალგორითმი, და ჩვენ გვქონდა, რომ სურათზე გამგეობის პირდაპირ წითელი ხაზი და სწორი ყვითელი ხაზი, ეს იყო მართლაც ალგორითმები, რომლებიც დიდი ო ო. იმის გამო, რომ იპოვოს მაიკ სმიტი სატელეფონო წიგნი n გვერდებზე, უარეს შემთხვევაში, შეიძლება მიიღოს ჩემთვის N ნაბიჯები. რაც შეეხება მიღების დასწრება? ერთი, ორი, სამი, ოთხი, ხუთი, ექვსი. რა არის ქრონომეტრაჟი ამ ალგორითმი აღების დასწრება? დიდი ო ო, რადგან თეორიულად მე უნდა აღვნიშნო, ყველას ოთახში. ახლა, როგორც განზე, რაც შეეხება სხვა ოპტიმიზაცია კვირაში ნულოვანი? ორი, ოთხი, ექვსი, რვა, 10, 12. კომპიუტერული მეცნიერი იქნებოდა გააცნობიეროს, დაველოდოთ წუთში, რომ არის ბრძანებით N დაყოფილი ორი ნაბიჯი. მარჯვენა? იმის გამო, რომ მე ვაკეთებ ორი ადამიანი დროს. მაგრამ ჩვენ ვაპირებთ იგნორირება იმ ქვედა წესრიგის თვალსაზრისით, და ჩვენ უბრალოდ აპირებს გადაყარეთ გაყოფა 2, და უბრალოდ ამბობენ, დიდი ო ო რომ ალგორითმი ისევე. რა ამ ერთი? ჩვენ გამოტოვოთ ზოგიერთი, მაგრამ რა იყო ალგორითმი, რომელიც იყო ჟურნალი ო? რომ აიღო უხეშად შესვლა N ნაბიჯები? გათიშე და დაიპყროთ. ზუსტად. ისევე როგორც სატელეფონო წიგნი მაგალითად კვირაში ნულოვანი და დღეს, სადაც ჩვენ გაყოფილი პრობლემა ისევ და ისევ და ისევ. ჩვენ მიიპყრო მას ფორუმში კვირაში ნულოვანი როგორც curved მწვანე ხაზი, და ჩვენ ვთქვით, რომ დღეს ეს იყო ლოგარითმული ალგორითმი. მართლაც, რიგი ზომების იგი სჭირდება შეასრულოს გათიშე და იბატონეს ან ორობითი ძებნის დავიწყებთ უწოდა, როგორც სატელეფონო წიგნი, არის ბრძანებით შესვლა და ნაბიჯები. და ეს არის ცოტა უცნაურია ერთი. რა ხდება ერთი ნაბიჯია, ან უფრო კონკრეტულად მუდმივი რიგი ნაბიჯები? შესაძლოა, ეს ორი, იქნებ ეს სამი, მაგრამ კომპიუტერის მეცნიერი მხოლოდ ამარტივებს მას, როგორც დიდი O 1, რამდენიმე მუდმივი რიგი ნაბიჯები. რა არის ის, რომ თქვენ შეიძლება გავაკეთოთ, რომ იღებს მუდმივი რიგი ნაბიჯები? რა არის ქრონომეტრაჟი ტაშს? მუდმივი დრო. მარჯვენა? ისევე როგორც, რა ქრონომეტრაჟი აკეთებს იმას, იღებს მხოლოდ ერთი ოპერაცია, როგორიცაა ბეჭდვა F Hello World. ეს შეიძლება ითქვას, რომ იყოს მუდმივი დროს, თუ არ ნაკლებად კუთხეში შემთხვევაში ბეჭდვითი F, რა შეიძლება ქრონომეტრაჟი ბეჭდვითი F რეალურად იყოს? და რატომ? რა არის n საზომი ამ შემთხვევაში? აუდიტორია: [INAUDIBLE]. დევიდ ჯ Malan: ზუსტად. რაოდენობის სიმბოლოებს ჩვენ გვინდა ბეჭდვა. ასე რომ, ეს არის ძალიან კონტექსტში მგრძნობიარე. დღეს, ჩვენ უკვე აქცენტი ბევრი წერილები და ციფრები აქ ფორუმში. მაგრამ ეს შეიძლება იყოს სიმბოლოების ფაქტობრივი სიმებიანი. გამოდის, რომ კიდევ ერთი ღონისძიება, რომელიც დაიწყება ზრუნვა, და რომ, პირიქით დიდი O, ასე ვთქვათ. ეს არის ის, omega ნოტაცია. ვინაიდან დიდი O ნიშნავს რა, რომ ზედა ზღვარი თქვენი ქრონომეტრაჟი? მაქსიმალურად, რამდენი დრო შეიძლება რაღაც მიიღოს? Omega-- ბოდიში ამ ინახავს მოდის up-- არის საპირისპირო, რომ, რომლითაც ეს ქვედა შეკრული შესახებ დროის რაღაც შეიძლება მიიღოს. ასე რომ. მაგალითად, რა არის ალგორითმი რომელიც იღებს ყოველთვის n კვადრატში ნაბიჯები? ისე, ერთი ალგორითმის ჩვენ ვნახეთ დღეს, ფაქტობრივად, შეიძლება იყოს, რომ ისევე. შერჩევა ერთგვარი. შერჩევა დალაგების საკმაოდ სულელური. მაშინაც კი, თუ ალგორითმი ბოდიში, მაშინაც კი, იმ შემთხვევაში, თუ მასივი უკვე დახარისხებული, შერჩევის დალაგების აპირებს შენარჩუნება გავლით სიაში დარწმუნდით, რომ იგი აქვს პატარა ელემენტი ისევ და ისევ და ისევ. და მიუხედავად იმისა, ადამიანები იმ აუდიტორიის ვიცი, რომ, დაველოდოთ წუთში, თქვენ უკვე გაიარა პატარა ელემენტს, კომპიუტერი არ იცის, რომ სანამ ეს გამოიყურება ყველა გზა მეშვეობით სიაში. ანალოგიურად, ქვედა ზღვარი, რომ ასევე შეიძლება მხედველობაში შეიძლება იყოს ხაზოვანი დრო. რამდენი დრო სჭირდება დალაგების N ელემენტების საუკეთესო საქმე გამოყენებით რაღაც ბუშტი დალაგება? დავუშვათ თქვენს სიაში უკვე დახარისხებული. ჩვენ ვთქვით, bubble sort იღებს ბრძანებით n კვადრატში ნაბიჯები. მაგრამ რა, თუ ეს უკვე გადანაწილებული? რა მოხდება, თუ ხვდები, მას შემდეგ, რაც ერთი გადის მასივი რომ თქვენ არ გააკეთა სვოპების? ნუ თქვენ უნდა შევინარჩუნოთ მიღების მეტი შეჭრა? No. ასე რომ ქვედა შეკრული on bubble sort შეიძლება ითქვას, რომ იყოს სწორხაზოვანი. Omega ო. და ჩვენ შეგვიძლია შევხედოთ სხვები ამ ისევე. მოდით მიიღოს სწრაფი შევხედოთ მხოლოდ ვიზუალიზაცია აქ თუ რამდენად ამ გამორჩეულნი. მე ვაპირებ ქვევით აქ ამ გვერდი, რომელიც შესაძლებელია C50 ნახვა, მაგრამ ეს იქნება ტკივილი მისაღებად მუშაობს, მას შემდეგ, რაც იგი იყენებს ტექნოლოგია მოუწოდა ჯავა აპლეტები, რომელიც არის დიდწილად არარეალიზებული ამ დღეებში, სულ ცოტა, Chrome და სხუანი. და ნება მომეცით წავიდეთ წინ და დააჩქაროს ეს და ახსნა, თუ რა ხდება. ეს არის დემონსტრირება bubble დალაგების, პირველი ალგორითმის ჩვენ შევხედეთ. და ეს ვიზუალიზაცია, რომ თითოეული ამ ბარები წარმოადგენს რაოდენობა. უფრო დიდი ბარი, უფრო დიდი რაოდენობა. პატარა ბარი, პატარა ნომერი. და რას ხედავთ ვიზუალურად, მაშინაც კი, მიუხედავად იმისა, რომ ეს ხდება სუპერ სწრაფი, ის არის, რომ წითელი ბარი, ისევე როგორც მე, ფეხით უკან და მეოთხე აფიქსირებს პრობლემები. თქვენ ხედავთ, რომ დიდი ელემენტები მართლაც bubbling მდე მარჯვენა, და პატარა ელემენტები არიან bubbling მდე მარცხენა. და ქვემოთ აქ, თუ ჩვენ რეალურად უფრო მჭიდროდ, ჩვენ შეგვიძლია რეალურად ითვლიან ნომერი შედარება და სხვ რომ სრულდებოდა. მაგრამ ამის ნაცვლად, მოდით შევხედოთ მეორე ალგორითმი ჩვენ შევხედე ადრე ჩვენს მოხალისეები, შერჩევა ერთგვარი. ვიზუალურად, მას აქვს ძალიან განსხვავებული ეფექტი. მაგრამ ეს, კიდევ ერთხელ, ძალიან ინტუიტიური, in რომ ჩვენ შევინარჩუნოთ შერჩევის შემდეგი ყველაზე პატარა ელემენტს, და მივიღეთ პატარა გაუმართლა. რომ იგრძნო, ფუნდამენტურად სწრაფად. მაგრამ, თუ ჩვენ გაიქცა ეს ისევ და ისევ და ისევ უამრავი საშუალებებით, ჩვენ ვხედავთ, რომ ეს მართლაც ჯერ კიდევ დიდი O of n კვადრატში. მოდით, გავაკეთოთ ერთი ბოლო აქ, Insertion დალაგების, რომელიც იყო მესამე ალგორითმი ჩვენ შევხედე, და გავიხსენოთ რომ ეს ერთი ეხება ელემენტები, როგორც ეს შეტაკებები მათ, მაგრამ მაშინ ეს, შესაძლოა, ცვლილებები, რამ მეტი, რათა ოთახში, ჩასმის ელემენტები სადაც მათ ეკუთვნის. ესეც მთავრდება მიცემის საბოლოო შედეგი. ახლა სამივე იმ იგრძნო საკმაოდ სწრაფად. და მართლაც, მე გაიქცა მათ დროს საკმაოდ კარგი კლიპი. მაგრამ ძირეულად, ისინი ყველა საკმაოდ საშინელი, რომ იყოს პატიოსანი. ყველა ეს ალგორითმები დღემდე რომ აწარმოებს დიდი O of n კვადრატში საკმაოდ ცოტა დრო, რომ აწარმოებს ბოლომდე. და მართლაც, ჩვენ ვხედავთ, და ვგრძნობ, რომ ეს ბოლოს თუ მე დახევის up ამ მესამე და საბოლოო დემო. ეს არის კიდევ ერთი ვიზუალიზაცია, რომ აპირებს რათა ნახოთ bubble sort მარცხენა, შერჩევის დალაგების შუა, და რაღაც, როგორც ერთ-ერთი ჩვენი მხრივ ბადებს ადრე შესთავაზა, შერწყმა დალაგების უფლება. გათიშე და დაიპყროთ სტრატეგია უფლება. და ეს არის, ფაქტობრივად, რაც ჩვენ ვაპირებთ შევხედოთ ოთხშაბათს. მაგრამ მოდით დროს ეს აწარმოებს პარალელურად. ეს არის დაახლოებით იგივე რაოდენობის ელემენტები, ყველა გაშვებული, ამავე დროს. Bubble დალაგების vs შერჩევა დალაგების vs შერწყმა დალაგების. ახლა, ისინი ყველა გაშვებული თეორიულად, ამავე დროს. პროცესორის მიმდინარეობს იგივე სიჩქარით, მაგრამ შეგიძლიათ გრძნობენ, რამდენად მოსაწყენია ეს არის ძალიან სწრაფად უნდა გახდეს, და რამდენად სწრაფად, როდესაც ჩვენ მიეცეს ცოტა კვირაში ნულოვანი ის ალგორითმები შეუძლია ჩვენ დაჩქარდეს რამ მდე. ახლა მოდით შევადაროთ ეს ერთ-ერთი ბოლო სახით. მე ვაპირებ წავიდეთ წინ CS50 ნახვა, სადაც ჩვენ გვაქვს ეს საბოლოო ბმული დღეს, სადაც ვინმე ინტერნეტში გთხოვთ ერთად ვიდეო, რომელიც იღებს რა სხვადასხვა დახარისხება ალგორითმები ჟღერს. ეს არის Insertion დალაგების. [Beeping] ამასთან, თქვენ მსჯელობა სიხშირე საფუძველზე სიმაღლე ბარი ბარი. ეს არის bubble sort. [უკუღმართი Beeping] ახლოვდება შემდეგი is-- მოდის მომავალი is-- შერჩევის დალაგების, სადაც კიდევ ერთხელ, ჩვენ შერჩევით შემდეგი ყველაზე პატარა ელემენტი, და ჩვენ ვხედავთ, რომ იზრდება მარცხნიდან მარჯვნივ. შერწყმა დალაგების, ჩვენი გამარჯვებული დღემდე დღეს. ყურადღება მიაქციეთ, როგორ ის გამყოფი რამ შევიდა [INAUDIBLE] ნახევარი და მეოთხედი. Gnome დალაგების, რომელიც ჩვენ არ გვაქვს ისაუბრა და ქმნის ვიზუალურად და audally ცოტა სხვადასხვა ფორმის და ხმა. უკან და მეოთხე, დასუფთავების რამ up. ასევე შეამოწმეთ heapsort ამ ბიჭს ნახვა. და ეს არის ის. ჩვენ ვნახავთ თქვენ მომავალი დრო. [Whooshing და მუსიკა]