>> [მუსიკის დაკვრა]
>> პროფესორი: ყველა უფლება.
ეს არის CS50 და ეს არის ბოლოს კვირაში სამი.
ასე რომ, ჩვენ დღეს აქ არ Sanders თეატრი, ნაცვლად Weidner ბიბლიოთეკა.
შიგნით რაც არის სტუდია ცნობილია, როგორც Hauser სტუდია,
ან უნდა ვთქვათ სტუდია H, ან უნდა ჩვენ ვთქვათ თუ სარგებლობდა, რომ ხუმრობა,
ეს ფაქტიურად კლასელი, Mark, ონლაინ,
რომელმაც შესთავაზა იმდენი გავლით Twitter.
ახლა რა მაგარი აქ ყოფნის სტუდიაში
ის არის, რომ მე გარშემორტყმული მწვანე კედლები, მწვანე ეკრანზე და chromakey,
ასე ვთქვათ, რაც იმას ნიშნავს, რომ CS50 ს წარმოების გუნდი, არ ვიცი მე
ახლა, შეიძლება აყენებს ჩემთვის ყველაზე მსოფლიოს ნებისმიერ წერტილში,
უკეთესი ან უარესი.
>> ახლა რა დევს წინ, პრობლემა კომპლექტი ორი არის თქვენს ხელში ამ კვირაში,
მაგრამ პრობლემა კომპლექტი სამი ამ ერთი კვირის განმავლობაში,
თქვენ უნდა დაუპირისპირდა ე.წ. თამაში 15
ძველი პარტიის სასარგებლოდ, რომ თქვენ ალბათ გახსოვთ მიმღები
როგორც ბავშვი, რომელიც მთელი bunch ციფრები, რომ შეიძლება ლღობას up, down,
მარცხენა და მარჯვენა, და იქ ერთი უფსკრული ფარგლებში თავსატეხი, სადაც თქვენ
შეიძლება რეალურად ლღობას იმ თავსატეხი ცალი.
საბოლოო ჯამში, თქვენ მიიღოს ამ თავსატეხი ნახევრად შემთხვევითი მიზნით,
და მიზანია დასალაგებლად ის, ზემოდან,
მარცხნიდან მარჯვნივ, ერთი ყველა გზა მეშვეობით 15.
>> სამწუხაროდ, განხორციელება თქვენ გაქვთ ხელთ
იქნება პროგრამული უზრუნველყოფა საფუძველზე, არ არის ფიზიკურად.
თქვენ რეალურად აპირებს უნდა დაწეროს კოდი, რომელიც სტუდენტი ან მომხმარებელს შეუძლია
ითამაშოს თამაში 15.
და სინამდვილეში, ჰაკერი გამოცემა თამაში 15
თქვენ უნდა იყოს გამოწვევა განხორციელება, არა მხოლოდ სათამაშო ამ ძველი სკოლა
თამაში, არამედ გადაჭრის ის, ახორციელებს ღმერთი რეჟიმი,
ასე ვთქვათ, რომ რეალურად წყვეტს თავსატეხი ადამიანის,
მათთვის მინიშნება, მას შემდეგ, რაც მინიშნება, მას შემდეგ, რაც მინიშნება.
ასე უფრო, რომ მომავალ კვირას.
მაგრამ ეს, რა ელის.
>> ახლა გავიხსენოთ, რომ ადრე ამ კვირას ჩვენ გვქონდა ამ cliffhanger, თუ გნებავთ,
რომლის დროსაც საუკეთესო ვაკეთებდით დახარისხება ბრძენი იყო ზედა ზღვარი დიდი ო ო
კვადრატი.
სხვა სიტყვებით, bubble sort, შერჩევის დალაგების, Insertion დალაგების,
ყველა მათგანი, ხოლო სხვადასხვა მათი განხორციელება,
devolved შევიდა n კვადრატში გაშვებული დრო ძალიან ცუდ შემთხვევაში.
და ჩვენ, როგორც წესი, ვივარაუდოთ, რომ ძალიან ცუდ შემთხვევაში დახარისხება
ერთ-ერთი, რომელიც თქვენი პორტები სრულიად უკან.
და მართლაც, დასჭირდა საკმაოდ რამდენიმე ნაბიჯი განახორციელოს თითოეული იმ ალგორითმები.
>> ახლა ბოლომდე კლასის გავიხსენოთ, ჩვენ შედარებით bubble sort
წინააღმდეგ შერჩევის დალაგების წინააღმდეგ ერთ სხვა რომ ჩვენ მოუწოდა შერწყმა დალაგების დროს,
და მე ვთავაზობ, რომ ის აღების უპირატესობა გაკვეთილი კვირაში
ნულოვანი, გათიშე და დაიპყროთ.
და რატომღაც მისაღწევად გარკვეული სახის ლოგარითმული ქრონომეტრაჟი საბოლოო ჯამში,
ნაცვლად რაღაც რომ წმინდა კვადრატული.
და ეს არ არის საკმაოდ ლოგარითმული, ეს ცოტა მეტია.
მაგრამ თუ გავიხსენებთ კლასი, ეს იყო ბევრად, ბევრად უფრო სწრაფად.
მოდით შევხედოთ, სადაც ჩვენ შეჩერდით.
>> Bubble დალაგების წინააღმდეგ შერჩევა დალაგების წინააღმდეგ შერწყმა დალაგების.
ახლა ისინი ყველა გაშვებული, თეორიულად, ამავე დროს.
პროცესორი არის გაშვებული, ამავე სიჩქარე.
მაგრამ თქვენ შეგიძლიათ გრძნობენ, რამდენად მოსაწყენია ეს ძალიან სწრაფად უნდა გახდეს,
და რამდენად სწრაფად, როდესაც ჩვენ მიეცეს ცოტა კვირაში ნულოვანი ის ალგორითმები,
შეგვიძლია დაჩქარდეს რამ მდე.
>> ასე ნიშნის ერთგვარი გამოიყურება საოცარი.
როგორ შეგვიძლია ბერკეტი მას, რათა დასალაგებლად ნომრები უფრო სწრაფად.
ისე, მოდით ვიფიქროთ უკან რომ ნივთიერება, რომელიც ჩვენ
ჰქონდა უკან კვირაში ნულოვანი, რომ ეძებს ვინმეს სატელეფონო წიგნი,
და გავიხსენოთ, რომ pseudocode რომ ჩვენ შეთავაზებული,
მეშვეობით, რომელიც ჩვენ შეგვიძლია მოვძებნოთ ვინმეს მოსწონს მაიკ სმიტი,
ჩანდა ცოტა რაღაც მსგავსი.
>> ახლა შევხედოთ კერძოდ ხაზი 7 და 8 და 10 და 11,
რომელიც გამოიწვევს, რომ მარყუჟი, რომლითაც ჩვენ ინახება ბრუნდება ხაზი 3 ისევ და ისევ,
და ისევ.
მაგრამ აღმოჩნდება, რომ ჩვენ შეგიძლიათ ნახოთ ეს ალგორითმი, აქ pseudocode,
ცოტა მეტი holistically.
ფაქტობრივად, რაც მე ვეძებ განთავსებულია აქ ეკრანზე,
ალგორითმი ეძებს მაიკ სმიტი შორის რამდენიმე კომპლექტი გვერდებზე.
და მართლაც, ჩვენ შეგვიძლია გავამარტივოთ ეს ალგორითმი იმ ხაზების 7 და 8,
და 10 და 11 უბრალოდ ვთქვა, რომელიც მე აქ წარმოდგენილი ყვითელი.
სხვა სიტყვებით, თუ მაიკ სმიტი ადრე წიგნი,
ჩვენ არ უნდა მიუთითოთ ნაბიჯი ნაბიჯ ახლა როგორ უნდა წავიდეთ პოულობენ მას.
ჩვენ არ უნდა მიუთითოთ დაბრუნდეს ხაზი 3,
რატომ არ გვაქვს მხოლოდ ნაცვლად, ვთქვათ, უფრო ზოგადად,
ძიება Mike წელს მარცხენა ნახევარში წიგნი.
>> პირიქით, თუ მაიკ რეალურად მოგვიანებით წიგნი,
რატომ არ ჩვენ უბრალოდ შეთავაზება unquote ძიება მაიკ მარჯვენა ნახევარში წიგნი.
სხვა სიტყვებით, რატომ არ გვაქვს მხოლოდ სახის punt საკუთარ თავს და განაცხადა,
ძიება Mike ამ სუბსეტ წიგნი,
და დატოვოს ის ჩვენი არსებული ალგორითმი გვითხრათ
როგორ ვიპოვოთ მაიკ რომ მარცხენა ნახევარში წიგნი.
სხვა სიტყვებით რომ ვთქვათ, ჩვენი ალგორითმი მუშაობს თუ არა ის
სატელეფონო წიგნი ამ სისქე, ამ სისქე, ან ნებისმიერი სისქის განაწილებაზე.
ასე რომ ჩვენ შეგვიძლია რეკურსიული განისაზღვროს ამ ალგორითმი.
სხვა სიტყვებით, წლის ეკრანზე აქ, არის ალგორითმი
ეძებს მაიკ სმიტი შორის გვერდების სატელეფონო წიგნი.
ასე რომ ხაზის 7 და 10, მოდით უბრალოდ, ვამბობთ ზუსტად რომ.
და მე ეს ტერმინი მომენტში წინ, და მართლაც, უკან
არის buzzword ახლა, და ეს არის ამ პროცესში
თავისსავე ციკლური მიერ რატომღაც გამოყენებით კოდი, რომ თქვენ უკვე გაქვთ,
და მას კიდევ ერთხელ, და ისევ და ისევ.
ახლა ეს იქნება მნიშვნელოვანი რომ ჩვენ რაღაცნაირად ბოლოში
გარეთ, და არ გავაკეთოთ, რომ უსასრულოდ გრძელი.
წინააღმდეგ შემთხვევაში, ჩვენ ვაპირებთ აქვს მართლაც უსასრულო ციკლი.
მაგრამ ვნახოთ, თუ ჩვენ შეგვიძლია სესხება ამ იდეას ერთი უკან, თავისსავე ისევ
და ისევ და ისევ, უნდა გადაწყვიტოს დახარისხება პრობლემა მეშვეობით შერწყმა
დალაგების, ყველა უფრო ეფექტურად.
>> ამიტომ მე გაძლევთ შერწყმა დალაგების.
მოდით შევხედოთ.
ასე რომ, აქ არის pseudocode, ერთად რომელიც ჩვენ შეგვიძლია განვახორციელოთ დახარისხება,
გამოყენებით ამ ალგორითმი მოუწოდა შერწყმა დალაგების.
და ეს საკმაოდ მარტივია.
On შეტანის ო ელემენტები, სხვა სიტყვებით, თუ თქვენ
მოცემული n ელემენტებს და ციფრები და წერილები და რაც არ უნდა შეყვანის,
თუ თქვენ მოცემული n ელემენტებს, თუ n ნაკლებია, ვიდრე 2, დააბრუნებს.
მარჯვენა?
იმიტომ, რომ თუ n ნაკლებია, ვიდრე 2, იმას ნიშნავს, რომ ჩემს სიაში ელემენტები
ან ზომა 0 ან 1, და ორივე იმ ტრივიალური შემთხვევაში,
სია უკვე დახარისხებული.
თუ არ არის სიაში, ის გადანაწილებული.
და თუ არ არის სია ხანგრძლივობა 1, ეს აშკარად გადანაწილებული.
ასე რომ, ალგორითმი მხოლოდ სჭირდება მართლაც რაღაც საინტერესო,
თუ ჩვენ გვაქვს ორი ან მეტი ელემენტები მოცემულია ჩვენთვის.
მოდით შევხედოთ ჯადოსნური შემდეგ.
Else დასალაგებლად მარცხენა ნახევარში ელემენტები, მაშინ დასალაგებლად მარჯვენა ნახევარში ელემენტები,
შემდეგ შერწყმა დახარისხებული halves.
და რა სახის გონება bending აქ ის არის, რომ მე ნამდვილად არ
როგორც ჩანს, არ გითხარით, არაფერი უბრალოდ არ არის, უფლება?
ყველა მე განაცხადა, მოცემული სია ო ელემენტები, დასალაგებლად მარცხენა ნახევარში,
შემდეგ მარჯვენა ნახევარში, მაშინ შერწყმა დახარისხებული halves,
მაგრამ სად არის ფაქტობრივი საიდუმლო სოუსით?
სად არის ალგორითმი?
ისე გამოდის, რომ ეს ორი ხაზი პირველი, დალაგება მარცხენა ნახევარში ელემენტები,
და სახის მარჯვენა ნახევარში ელემენტები, არის რეკურსიული მოუწოდებს, ასე ვთქვათ.
>> ყოველივე ამის შემდეგ, ამ მომენტში, მაქვს
ალგორითმი, რომლის დასალაგებლად მთელი bunch of ელემენტები?
დიახ.
ეს უფლება აქ.
ეს უფლება აქ ეკრანზე, და ასე რომ შეგიძლიათ გამოიყენოთ იგივე კომპლექტი ნაბიჯები
დასალაგებლად მარცხენა ნახევარში, როგორც შემიძლია მარჯვენა ნახევარში.
და მართლაც, ისევ და ისევ.
ასე რომ, რატომღაც ან სხვა, და ჩვენ მალე ეს, ჯადოსნური შერწყმა დალაგების
არის ჩართული, რომ ძალიან საბოლოო ხაზი, შერწყმის დახარისხებული halves.
და რომ, როგორც ჩანს, საკმაოდ ინტუიციური.
თქვენ მიიღოს ორ ნაწილად, და თქვენ, რატომღაც, შერწყმა მათ ერთად,
და ჩვენ დავინახავთ, ეს კონკრეტულად ამ მომენტში.
>> მაგრამ ეს არის სრული ალგორითმი.
და ვნახოთ, სწორედ ამიტომ.
ისე ვფიქრობ, რომ ჩვენ მოცემული ეს იგივე რვა ელემენტებს აქ ეკრანზე, ერთი
რვა, მაგრამ ისინი ერთი შეხედვით, შემთხვევითი მიზნით.
და მიზანი ხელთ არის დასალაგებლად ამ ელემენტებს.
ისე როგორ შემიძლია წასვლა შესახებ ამით ის გამოყენებით, კიდევ ერთხელ,
შერწყმა დალაგების, როგორც პოსტი ამ pseudocode?
ისევ და ისევ, ingrain ეს თქვენი აზრით, მხოლოდ ერთი წუთით.
პირველ შემთხვევაში საკმაოდ ტრივიალური, თუ ის არანაკლებ 2,
უბრალოდ დაბრუნებას, არ არსებობს სამუშაოა ჩასატარებელი.
ასე რომ, რეალურად არსებობს მხოლოდ სამი ნაბიჯები, რათა ნამდვილად გვახსოვდეს.
ისევ და ისევ, მე ვარ აპირებს გვინდა, რომ გვქონდეს
დასალაგებლად მარცხენა ნახევარში, დასალაგებლად მარჯვენა ნახევარში,
და კიდევ მათი ორ ნაწილად დალაგებულია,
მინდა შერწყმა მათ ერთად ერთ დახარისხებული სია.
გააგრძელეთ, რომ გონება.
>> ასე რომ, აქ ორიგინალური სიაში.
მოდით მკურნალობა, როგორც მასივი, როგორც ჩვენ დავიწყეთ
კვირაში ორი, რომელიც არის მომიჯნავე ბლოკი მეხსიერება.
ამ შემთხვევაში, რომელიც შეიცავს რვა ციფრები, თავში დაბრუნება უკან.
და მოდით ახლა ვრცელდება შერწყმა დალაგების.
ასე რომ, მე პირველად მინდა დასალაგებლად მარცხენა ნახევარში ამ სიაში,
და მოდით, აქედან გამომდინარე, ფოკუსირება 4, 8, 6, და 2.
>> ახლა როგორ შემიძლია წასვლა შესახებ დახარისხება სიაში ზომა 4?
მე უნდა ახლა განიხილავს დახარისხება მარცხნივ მარცხენა ნახევარში.
ერთხელ, მოდით გადახვევა მხოლოდ ერთი წუთით.
იმ შემთხვევაში, თუ pseudocode არის ეს, და მე ეძლევა რვა ელემენტები,
8 აშკარად დიდი მეტი ან ტოლია 2.
ასე რომ, პირველ შემთხვევაში არ ვრცელდება.
ასე რომ დასალაგებლად რვა ელემენტებს, მე პირველი დასალაგებლად მარცხენა ნახევარში ელემენტები,
მაშინ მე დასალაგებლად მარჯვენა ნახევარში, მაშინ მე შერწყმა ორი დახარისხებული ნაწილად, თითოეული ზომა 4.
OK.
>> მაგრამ თუ თქვენ უბრალოდ მითხრა, დასალაგებლად მარცხენა ნახევარში, რომელიც არის ზომა 4,
როგორ უნდა დასალაგებლად მარცხენა ნახევარი?
ისე, თუ მაქვს შეყვანის ოთხი ელემენტები,
მე პირველად დასალაგებლად მარცხენა ორი, მაშინ უფლება ორი,
და მერე შერწყმა მათ ერთად.
ასე რომ, კიდევ ერთხელ, ეს ხდება ცოტა გონება bending თამაში აქ,
იმიტომ, რომ თქვენ, სახის, უნდა მახსოვს, სადაც თქვენ ამბავი,
მაგრამ ბოლოს დღეს, მოცემული ნებისმიერი რაოდენობის ელემენტები,
თქვენ პირველი გვინდა დასალაგებლად მარცხენა ნახევარში, მაშინ მარჯვენა ნახევარში,
შემდეგ შერწყმა მათ ერთად.
მოდით დავიწყოთ ზუსტად რომ.
აი შეყვანის რვა ელემენტებს.
ამჟამად ჩვენ ვუყურებთ მარცხენა ნახევარში აქ.
როგორ დასალაგებლად ოთხი ელემენტები?
მე პირველად დასალაგებლად მარცხენა ნახევარში.
ახლა როგორ უნდა დასალაგებლად მარცხენა ნახევარი?
მე უკვე მოცემული ორი ელემენტები.
მოდით დასალაგებლად ამ ორ ელემენტს.
2 მეტია ან უდრის 2, რა თქმა უნდა.
ასე რომ, პირველ შემთხვევაში არ ვრცელდება.
>> ასე რომ, ახლა უნდა დასალაგებლად მარცხენა ნახევარი ამ ორი ელემენტები.
მარცხენა ნახევარში, რა თქმა უნდა, მხოლოდ 4.
ასე რომ, მე დასალაგებლად სიაში ერთ ელემენტს?
კარგად არის, რომ სპეციალური ბაზის შემთხვევაში დასაწყისშივე, ასე ვთქვათ, ვრცელდება.
1 2 დღეზე ნაკლები, და ჩემი სია მართლაც ზომა 1.
ასე რომ, მე უბრალოდ დაბრუნდეს.
მე არაფერს არ აკეთებს.
და მართლაც, შევხედოთ, თუ რა მე კეთდება, 4 უკვე დახარისხებული.
ისევე, როგორც მე უკვე ნაწილობრივ წარმატებული აქ.
>> ახლა, როგორც ჩანს, ასეთი სულელური აცხადებენ, მაგრამ ეს სიმართლეა.
4 სიაში ზომა 1.
ეს უკვე გადანაწილებული.
სწორედ მარცხენა ნახევარში.
ახლა მე დასალაგებლად მარჯვენა ნახევარში.
ჩემი შემავალი ერთ-ერთი ელემენტია, 8 ასევე, უკვე დახარისხებული.
Stupid, მაგრამ კიდევ ერთხელ, ამ ძირითად პრინციპს,
აპირებს საშუალებას მოგვცემს აშენება თავზე ამ წარმატებით.
4 დახარისხებული, 8 დალაგებულია, ახლა რა იყო, რომ ბოლო ნაბიჯი?
ასე რომ მესამე და საბოლოო ნაბიჯი, ნებისმიერ დროს თქვენ დახარისხება სიაში, გავიხსენოთ,
იყო შერწყმა ორ ნაწილად, მარცხენა და მარჯვენა.
ასე რომ, მოდით გავაკეთოთ ზუსტად რომ.
ჩემი მარცხენა ნახევარში, რა თქმა უნდა, 4.
ჩემი მარჯვენა ნახევარში 8.
>> ასე რომ, მოდით ეს.
პირველი მე ვაპირებ გამოყოს დამატებითი მეხსიერება,
რომ მე წარმოვადგენ, როგორც მხოლოდ მეორად მასივი,
რომ დიდი საკმარისი შეესაბამება ეს.
მაგრამ თქვენ წარმოიდგინეთ, გაგრძელების მართკუთხედი მთელ სიგრძეზე,
თუ ჩვენ გვჭირდება უფრო მოგვიანებით.
როგორ შემიძლია მიიღებს 4 და 8, და შერწყმა ამ ორი სიები ზომა 1 ერთად?
აქაც საკმაოდ მარტივია.
4 მოდის პირველი, შემდეგ მოდის 8.
იმიტომ, რომ თუ მინდა დასალაგებლად მარცხენა ნახევარში, მაშინ მარჯვენა ნახევარში,
და შემდეგ შერწყმა ამ ორი halves ერთად, დახარისხებული მიზნით,
4 მოდის პირველი, შემდეგ მოდის 8.
>> ასე რომ, ჩვენ, როგორც ჩანს, პროგრესის, მაშინაც კი, მიუხედავად იმისა, რომ მე არ კეთდება ნებისმიერი ფაქტობრივი მუშაობის.
მაგრამ გახსოვდეთ, სადაც ჩვენ ვართ ამბავი.
ჩვენ თავდაპირველად რვა ელემენტებს.
ჩვენ დახარისხებული მარცხენა ნახევარში, რომელიც 4.
მაშინ ჩვენ დახარისხებული მარცხენა ნახევარში მარცხენა ნახევარში, რომელიც 2.
და აქ ჩვენ მივდივართ.
ჩვენ გავაკეთეთ, რომ ნაბიჯი.
>> ასე რომ, თუ ჩვენ დახარისხებული მარცხენა ნახევარში 2, ახლა ჩვენ
უნდა დასალაგებლად მარჯვენა ნახევარში 2.
ასე რომ, მარჯვენა ნახევარში 2 ამ ორი ფასეულობის აქ, 6 და 2.
მოდით ახლა მიიღოს შეყვანის ზომა 2 და დასალაგებლად მარცხენა ნახევარი და შემდეგ
მარჯვენა ნახევარში, და შემდეგ შერწყმა მათ ერთად.
ისე როგორ უნდა დასალაგებლად სიაში ზომა 1, რომელიც შეიცავს მხოლოდ 6?
მე უკვე გააკეთა.
ეს სია, ზომა 1 დალაგებულია.
>> როგორ დასალაგებლად ერთი სია ზომა 1, ე.წ. მარჯვენა ნახევარში.
ისე, ძალიან, უკვე დახარისხებული.
ნომერი 2 მარტო.
ასე რომ, ახლა მე მაქვს ორი halves, მარცხენა და უფლება, მე უნდა შერწყმა მათ ერთად.
ნება მომეცით მისცეს თავს ზოგიერთი დამატებითი ფართი.
და 2 იქ, 6-იქ, რითაც
დახარისხება სიაში, მარცხენა და მარჯვენა, და შერწყმის ერთად, საბოლოო ჯამში.
ასე რომ, მე ოდნავ უკეთეს ფორმაში.
მე არ კეთდება, რადგან ნათლად 4, 8, 2, 6 არ არის საბოლოო შეკვეთით, რომ მინდა.
მაგრამ მე ახლა უკვე ორი სიები ზომა 2, ორივე, შესაბამისად, უკვე დახარისხებული.
ასე რომ, ახლა თუ გადახვევა თქვენი აზრით თვალი, სად რომ დაგვტოვებთ?
დავიწყე რვა ელემენტებს, მაშინ მე გახდნენ ის ქვემოთ მარცხენა ნახევარში 4,
შემდეგ მარცხენა ნახევარში 2, და შემდეგ მარჯვენა ნახევარში 2,
დავამთავრე, ამიტომ, დახარისხება მარცხენა ნახევარი 2, და მარჯვენა ნახევარში 2,
ასე რომ, რა არის მესამე და საბოლოო ნაბიჯი აქ?
მე უნდა გაერთიანდეს ორი სიები ზომა 2.
მოდით წავიდეთ წინ.
და ეკრანზე აქ, მისცეს ჩემთვის დამატებითი მეხსიერება,
თუმცა ტექნიკურად, შეამჩნია, რომ მე მივიღე მთელი bunch of ცარიელი სივრცე ზევით
არსებობს.
თუ მინდა, რომ იყოს განსაკუთრებით ქმედითი სივრცე ბრძენი,
მე შეიძლება მხოლოდ დაიწყოს მოძრავი ელემენტები უკან და მეოთხე, ზედა და ქვედა.
მაგრამ მხოლოდ ვიზუალური სიცხადე, მე ვაპირებ, რომ ეს ქვემოთ,
შენარჩუნება რამ ლამაზი და სუფთა.
>> ასე რომ, მე მაქვს ორი სიები ზომა 2.
პირველი სია 4 და 8.
მეორე სიაში აქვს 2 და 6.
მოდით შერწყმა იმ ერთად დახარისხებული მიზნით.
2, რა თქმა უნდა, მოდის პირველი, მაშინ 4, მაშინ 6, მაშინ 8.
და ახლა ჩვენ, როგორც ჩანს, მიღების სადღაც საინტერესო.
ახლა მე დახარისხებული ნახევარი სიაში, და ერთსა, ეს
ყველა კი ნომრები, მაგრამ ეს ნამდვილად, უბრალოდ დამთხვევა.
და მე ახლა დახარისხებული მარცხენა ნახევარში, ასე, რომ ეს არის 2, 4, 6, 8 და.
არაფერი არ არის მწყობრიდან.
ეს იგრძნობა პროგრესი.
>> ახლა ეს იგრძნობა მე უკვე საუბარი სამუდამოდ ახლა,
ასე რომ, რა რჩება ჩანს, თუ ეს ალგორითმი, მართლაც, უფრო ეფექტური.
მაგრამ ჩვენ ვაპირებთ მეშვეობით სუპერ მეთოდურად.
კომპიუტერი, რა თქმა უნდა, ამის გაკეთება, როგორიცაა, რომ.
ასე რომ, სად ვართ ჩვენ?
ჩვენ დავიწყეთ რვა ელემენტებს.
მე დახარისხებული მარცხენა ნახევარში 4.
მე, როგორც ჩანს უნდა გაკეთდეს, რომ.
ასე რომ, ახლა შემდეგი ნაბიჯი არის დასალაგებლად მარჯვენა ნახევარში 4.
და ამ ნაწილში ჩვენ შეგვიძლია წავიდეთ მეშვეობით ცოტა მეტი
სწრაფად, თუმცა თქვენ მისასალმებელი გადახვევა და პაუზის, უბრალოდ
ვფიქრობ მეშვეობით ეს საკუთარი ტემპით, მაგრამ რა
ახლა ჩვენ გვაქვს შესაძლებლობა, რომ ზუსტად იგივე ალგორითმი ოთხ
სხვადასხვა ნომრები.
>> ასე რომ, მოდით წავიდეთ წინ და ფოკუსირება მარჯვენა ნახევარში, რომელიც ჩვენ აქ ვართ.
მარცხენა ნახევარში, რომ მარჯვენა ნახევარში, და ახლა
მარცხენა ნახევარში მარცხენა ნახევარი რომ მარჯვენა ნახევარში,
და როგორ უნდა დასალაგებლად სიაში ზომა 1 შემცველი მხოლოდ ნომერი 1?
ეს უკვე გააკეთა.
როგორ გავაკეთო იგივე სია ზომა 1 შემცველი მხოლოდ 7?
ეს უკვე გააკეთა.
ნაბიჯი სამი ამ ნახევარი შემდეგ არის შერწყმა ამ ორი ელემენტები
ახალ სიაში ზომა 2, 1 და 7.
არ ჩანს, არ გაკეთებულა ყველა რომ ბევრი საინტერესო მუშაობა.
ვნახოთ, რა მოხდება შემდეგ.
მე უბრალოდ დალაგებულია მარცხენა ნახევარში მარჯვენა ნახევარში ჩემი ორიგინალური შეყვანა.
ახლა მოდით დასალაგებლად მარჯვენა ნახევარი, რომელიც შეიცავს 5 და 3.
მოდით კიდევ ერთხელ შევხედოთ მარცხენა ნახევარი, დახარისხებული, მარჯვენა ნახევარში, დახარისხებული,
და შერწყმა ამ ორი ერთად, ზოგიერთი დამატებითი სივრცე,
3 მოდის პირველი, შემდეგ მოდის 5.
ასე რომ, ახლა ჩვენ დახარისხებული მარცხენა ნახევარში მარჯვენა ნახევარში
ორიგინალური პრობლემა, და მარჯვენა ნახევარში მარჯვენა ნახევარში
ორიგინალური პრობლემა.
რა არის მესამე და საბოლოო ნაბიჯი?
ისე შერწყმა ამ ორი halves ერთად.
ნება მომეცით მიიღოს თავს დამატებითი ფართი, მაგრამ, კიდევ ერთხელ, მე
შეიძლება იყოს გამოყენებით, რომ თავისუფალ სივრცეში up დაბრუნება.
მაგრამ ჩვენ ვაპირებთ, რომ შევინარჩუნოთ ეს მარტივი ვიზუალურად.
მიადევნე თვალი შერწყმა ახლა 1, მაშინ 3 და შემდეგ 5, და შემდეგ 7.
ამით რის გამოც მე ახლა მარჯვენა ნახევარში ორიგინალური პრობლემა
რომ კარგად გადანაწილებული.
>> ასე რომ, რა რჩება?
ვგრძნობ, მე შენარჩუნება და განაცხადა, რომ იგივე რამ ისევ და ისევ,
მაგრამ ეს ამრეკლი ის ფაქტი, რომ ჩვენ გამოყენებით უკან.
პროცესი გამოყენებით ალგორითმი ისევ და ისევ,
პატარა subsets of ორიგინალური პრობლემა.
ასე რომ, ახლა აქვს მარცხენა დახარისხებული ნახევარი ორიგინალური პრობლემა.
მე მაქვს უფლება დახარისხებული ნახევარი ორიგინალური პრობლემა.
რა არის მესამე და საბოლოო ნაბიჯი?
ოჰ, ეს შერწყმით.
ასე რომ, მოდით გავაკეთოთ, რომ.
მოდით გამოყოს გარკვეული დამატებითი მეხსიერება, მაგრამ ჩემო, ჩვენ
ვერ დააყენა მას ვერსად ახლა.
ჩვენ გვაქვს იმდენად სივრცეში არსებული ჩვენთვის, მაგრამ ჩვენ გავაგრძელებთ მარტივი.
იმის ნაცვლად, რომ ბრუნდება და მეოთხე ჩვენი ორიგინალური მეხსიერება,
მოდით უბრალოდ ეს ვიზუალურად ქვემოთ აქ ქვემოთ,
დასრულდება up შერწყმის მარცხენა ნახევარში და მარჯვენა ნახევარში.
>> ასე რომ შერწყმის, რა უნდა გავაკეთოთ?
მე მინდა, რომ ელემენტები მიზნით.
ასე რომ, ეძებს მარცხენა ნახევარში, მე ვერ ვხედავ პირველი ნომერი 2.
მე შევხედოთ მარჯვენა ნახევარში, მე ვერ ვხედავ პირველი ნომერი
არის 1, ასე აშკარად, რომელიც ნომერი არ მინდა pluck გარეთ,
და პირველი ჩემი საბოლოო სიაში?
რა თქმა უნდა, 1.
ახლა მინდა ვთხოვო, რომ იგივე კითხვა.
მარცხენა ნახევარში, მე მაინც ნომერი 2.
მარჯვენა ნახევარში, მაქვს ნომერი 3.
რომელი მინდა აირჩიოს?
რა თქმა უნდა, ნომერი 2 ახლა შეამჩნია კანდიდატები
4 მარცხენა, 3 მარჯვენა.
მოდით, რა თქმა უნდა, აირჩიოს 3.
ახლა კანდიდატები არიან 4 მარცხენა, 5 მარჯვენა.
ჩვენ, რა თქმა უნდა, აირჩიოს 4.
6 მარცხენა, 5 მარჯვენა.
ჩვენ, რა თქმა უნდა, აირჩიოს 5.
6 მარცხენა, 7 უფლება.
ჩვენ ვირჩევთ 6, და მაშინ ჩვენ აირჩიეთ 7 და შემდეგ ჩვენ ვირჩევთ 8.
Voila.
>> ასე რომ, დიდი რაოდენობით სიტყვა შემდეგ, ჩვენ დახარისხებული ამ სიაში რვა ელემენტებს
შევიდა სიაში ერთი გზით რვა, რომ იზრდება ყოველი ნაბიჯი,
მაგრამ რამდენ დროს გააკეთა ის გვაძლევს, რომ.
ისე მე შეგნებულად დაგებულ რამ, ხატოვნად
აქ, ასე რომ ჩვენ შეგვიძლია სახის ვხედავ და ვაფასებ სამმართველოს
დაპყრობის რომ ხდებოდა.
>> მართლაც, თუ თქვენ ვიხსენებთ იმ ფონზე, მე დაუტოვებიათ ყველა ამ dotted ხაზები
ამ ადგილის მფლობელებს, შეგიძლიათ, სახის, ვხედავ, საპირისპირო მიზნით,
თუ სახის ვიხსენებთ ისტორია ახლა, ჩემი ორიგინალური სიაში
არის, რა თქმა უნდა, ზომა 8.
და მაშინ ადრე, მე ვიყავი საქმე ორი სიები ზომა 4,
და შემდეგ ოთხი სიები ზომა 2, და შემდეგ რვა სიები ზომა 1.
>> ასე რომ, რას ნიშნავს ეს, სახის, შეგახსენოთ?
ისე, რა თქმა უნდა, ნებისმიერ ალგორითმები ჩვენ
შევხედე ჯერჯერობით, სადაც ჩვენ გათიშე და გაყოფა, და გაყოფა,
შენარჩუნება მქონე რამ კიდევ ერთხელ, და ერთხელ, იწვევს ამ ზოგადი იდეა.
ასე რომ იქ რაღაც ლოგარითმული ხდება აქ.
და ეს არ არის საკმაოდ ჟურნალი n, მაგრამ იქ ლოგარითმული კომპონენტი
ის, რაც ჩვენ უბრალოდ გაკეთდეს.
>> ახლა განვიხილოთ, თუ როგორ არის სინამდვილეში.
ასე რომ შეხვიდეთ ო, ერთხელ იყო დიდი ქრონომეტრაჟი,
როდესაც ჩვენ გავაკეთეთ რაღაც ორობითი ძებნა, როგორც ჩვენ ახლა უწოდებენ,
გათიშე და დაპყრობას სტრატეგია მეშვეობით, რომელიც ჩვენ ვნახეთ, მაიკ სმიტი.
ახლა ტექნიკურად.
ეს არის ის, ჟურნალი ბაზა 2 ო, მაშინაც კი, მიუხედავად იმისა, რომ ყველაზე მათემატიკის გაკვეთილებს,
10, როგორც წესი, ბაზა, რომ თქვენ ვივარაუდოთ.
მაგრამ კომპიუტერის მეცნიერები თითქმის ყოველთვის ვფიქრობ და გაიგო თვალსაზრისით ბაზა 2,
ასე რომ, ჩვენ, როგორც წესი, უბრალოდ, ვამბობთ ლოგი n, ნაცვლად ჟურნალი ბაზა 2 ო,
მაგრამ ისინი ზუსტად ერთი და იმავე წელს მსოფლიოში კომპიუტერული
მეცნიერებისა და როგორც განზე, არსებობს მუდმივი ფაქტორი
განსხვავება ორ, ასე რომ სადაო მაინც, უფრო ფორმალური მიზეზის გამო.
>> მაგრამ ახლა, რაც ჩვენ აღელვებს არის ეს მაგალითი.
მოდით არ ადასტურებს მაგალითად, მაგრამ ცოტა გამოყენება, მაგალითად, ნომრები
ხელთ, როგორც საღი აზრის შემოწმება, თუ გნებავთ.
ასე რომ, ადრე ფორმულა ჟურნალი ბაზა 2 ო, მაგრამ რა არის n ამ შემთხვევაში.
მე მქონდა n ორიგინალური ნომრები, ან 8 ორიგინალური ნომერი კონკრეტულად.
ახლა ეს უკვე ცოტა ხოლო, მაგრამ მე საკმაოდ
დარწმუნებული ვარ, რომ ჟურნალი ბაზა 2 ღირებულება 8: 3,
და მართლაც, რა ლამაზი, რომ ის არის რომ 3 ზუსტად რაოდენობის ჯერ
რომ თქვენ შეგიძლიათ დაყოფის სია სიგრძე 8 ისევ და ისევ,
და ისევ, სანამ თქვენ დარჩა სიები უბრალოდ ზომა 1.
მარჯვენა?
8 მიდის 4, მიდის 2, მიდის 1, და ეს
ამრეკლი ზუსტად რომ სურათი გვქონდა მხოლოდ ერთი წუთით წინ.
ასე ცოტა საღი აზრის შეამოწმოს, თუ სად ლოგარითმი რეალურად ჩართული.
>> ასე რომ, ახლა, რა არის ჩართული აქ? n.
ასე რომ შეამჩნია, რომ ყოველ დროს მე გაყოფილი სიაში,
თუმცა საპირისპირო მიზნით ისტორიაში აქ, მე მაინც აკეთებს N რამ.
ეს შერწყმის ნაბიჯი საჭირო, რომ მე შეხება ყოველ ერთ ნომრები,
იმისათვის, რომ ლღობას ის მისი შესაბამის ადგილას.
ასე რომ, მიუხედავად იმისა, რომ სიმაღლე ამ სქემა არის ზომა შესვლა n n ან 3,
კონკრეტულად, სხვა სიტყვებით, მე სამი დივიზია აქ.
რამდენი სამუშაო გავაკეთო ჰორიზონტალურად გასწვრივ გრაფიკი ყოველ ჯერზე?
>> ისე, მე n ნაბიჯები მუშაობა, იმიტომ, რომ თუ მე
ოთხი ელემენტები და ოთხი ელემენტები, და მე უნდა შერწყმა მათ ერთად.
მე უნდა გაიაროს ამ ოთხი და ამ ოთხი,
საბოლოოდ შერწყმა მათ ისევ რვა ელემენტებს.
თუ პირიქით მაქვს რვა თითების აქ, რომელიც მე არ, და რვა
fingers-- ბოდიში თუ მე ოთხი თითების მეტი აქ,
რომელიც მე, ოთხი თითი აქ, რომელიც მე,
მაშინ, რომ იგივე მაგალითად, როგორც ადრე, თუ ამის გაკეთება
რვა თითების თუმცა სულ, რაც შემიძლია, სახის, გააკეთოს.
მე შემიძლია ზუსტად აქ, მაშინ მე რა თქმა უნდა,
შერწყმა ყველა ამ სიებს ზომა 1 ერთად.
მაგრამ მე, რა თქმა უნდა გამოიყურებოდეს თითოეულ ელემენტს ზუსტად ერთხელ.
სიმაღლე ეს პროცესი შესვლა N, სიგანე ამ პროცესში, ასე ვთქვათ,
N, ასე რომ, ჩვენ, როგორც ჩანს, აქვს, საბოლოო ჯამში, არის
გაშვებული დრო ზომა N ჯერ შესვლა n.
>> სხვა სიტყვებით, ჩვენ გაყოფილი სია, შესვლა N ჯერ,
მაგრამ ყოველ ჯერზე ჩვენ გავაკეთეთ, ჩვენ გვქონდა შეეხოთ ყველა ერთი ელემენტები
იმისათვის, რომ შერწყმა მათ ყველა ერთად, რომელიც
იყო ო ნაბიჯი, ამიტომ ჩვენ გვაქვს N ჯერ შესვლა n, ან როგორც კომპიუტერის მეცნიერი ვიტყოდი,
asymptotically, რომელიც იქნება დიდი სიტყვა
აღწერს ზედა შეკრული გაშვებული დროს,
ჩვენ გაშვებული დიდი o შესვლა n დროს, ასე ვთქვათ.
>> ახლა ეს არის მნიშვნელოვანი, რადგან გავიხსენოთ, რა გაშვებული ჯერ
ბუშტი დალაგების, და შერჩევის დალაგების, და Insertion დალაგების,
და კიდევ რამდენიმე სხვა, რომ არსებობს, N კვადრატში იყო, სადაც ჩვენ ვიყავით.
და თქვენ შეგიძლიათ, სახის, რომ ეს აქ.
თუ n კვადრატში აშკარად N ჯერ n, მაგრამ აქ ჩვენ გვაქვს N ჯერ შესვლა n,
და ჩვენ უკვე ვიცით კვირაში ნულოვანი, რომ ჟურნალი ო, ლოგარითმული,
უკეთესია, ვიდრე რაღაც წრფივი.
ყოველივე ამის შემდეგ, გავიხსენოთ სურათი წითელი და ყვითელი
და მწვანე ხაზები, რომ ჩვენ გაამახვილა, რომ მწვანე ლოგარითმული ხაზი გაცილებით ნაკლები იყო.
და, შესაბამისად, ბევრად უკეთესი და უფრო სწრაფად ვიდრე პირდაპირ ყვითელი და წითელი ხაზები,
N ჯერ შესვლა n არის, რა თქმა უნდა, უკეთესი ვიდრე n ჯერ n, ან N კვადრატში.
>> ასე რომ, ჩვენ, როგორც ჩანს, განსაზღვრული ალგორითმი შერწყმა
ერთგვარი, რომელიც მართავს ბევრი სწრაფად დრო, და მართლაც,
სწორედ ამიტომ, ამ კვირაში, როდესაც ჩვენ ვნახეთ, რომ კონკურსში შორის bubble
დალაგების, შერჩევის დალაგების, და შერწყმა დალაგების, შერწყმა დალაგების ნამდვილად, ნამდვილად გაიმარჯვა.
და მართლაც, ჩვენ კი არ დაველოდოთ ამისთვის bubble sort და შერჩევის დალაგება
უნდა დაასრულოს.
>> ახლა მოდით ერთი სხვა უღელტეხილზე ამ, ოდნავ მეტი
ფორმალური თვალსაზრისით, მხოლოდ შემთხვევაში, ეს ეხმიანება უკეთესი
ვიდრე, რომ უფრო მაღალი დონის დისკუსიაში.
ასე რომ, აქ ალგორითმი ერთხელ.
მოდით, ვკითხოთ საკუთარ თავს, რა ქრონომეტრაჟი
არის ამ ალგორითმები სხვადასხვა ნაბიჯები?
მოდით ეს გაყოფა პირველი შემთხვევაში და მეორე შემთხვევაში.
თუ და სხვაგან IF შემთხვევაში, IF n ნაკლებია, ვიდრე 2, დააბრუნებს.
იგრძნობა მუდმივი დრო.
ეს, სახის, როგორც ორი ნაბიჯი IF n ნაკლებია, ვიდრე 2, შემდეგ დაბრუნდნენ.
მაგრამ, როგორც ჩვენ განაცხადა ორშაბათს, მუდმივი, ან დიდი o 1,
შეიძლება ორი ნაბიჯი, სამი ნაბიჯები, თუნდაც 1,000 ნაბიჯები.
რა მნიშვნელობა აქვს არის ის, რომ მუდმივი რიგი ნაბიჯები.
ასე რომ, ყვითელი ხაზი გაუსვა pseudocode აქ გადის, ჩვენ მოვუწოდებთ მას,
მუდმივი დრო.
ასე რომ, უფრო მეტად, და ჩვენ ვაპირებთ ამ
იქნება იმდენად, რამდენადაც ჩვენ გააფორმოს ეს უფლება, ახლა ტ ო,
ქრონომეტრაჟი პრობლემა რომელიც იღებს n somethings როგორც შეყვანის,
უდრის დიდი o ერთი, თუ n ნაკლებია, ვიდრე 2.
ასე რომ, ეს პირობითი, რომ.
ასე რომ იყოს ნათელი, თუ n ნაკლებია, ვიდრე 2, ჩვენ გვაქვს ძალიან მოკლე ჩამონათვალი, მაშინ
ქრონომეტრაჟი, ტ ო, სადაც n 1 ან 0, სწორედ ამ კონკრეტულ შემთხვევაში,
ეს იქნება მუდმივი დრო.
იგი აპირებს მიიღოს ერთი ნაბიჯი, ორი ნაბიჯი, რასაც.
ეს არის ფიქსირებული რაოდენობის ნაბიჯები.
>> ასე რომ, წვნიანი ნაწილი უნდა აუცილებლად უნდა იყოს სხვა შემთხვევაში, pseudocode.
სხვაგან საქმე.
Sort მარცხენა ნახევარში ელემენტები, ერთგვარი უფლება ნახევარი ელემენტები, შერწყმა დახარისხებული halves.
რამდენი ხანი თითოეული იმ ნაბიჯებს?
ისე, თუ გაშვებული დრო დასალაგებლად N ელემენტები
არის, მოდით, მას ძალიან generically, ტ ო,
შემდეგ დახარისხება მარცხენა ნახევარში ელემენტები
არის, სახის, როგორც ამბობდა, T ო იყოფა 2,
და ანალოგიურად დახარისხება მარჯვენა ნახევარში ელემენტები არის, სახის, როგორც ამბობდა,
ტ ო იყოფა 2, ხოლო შემდეგ შერწყმის დახარისხებული halves.
თუ მე მაქვს რამდენიმე რიგი ელემენტები აქ,
ისევე როგორც ოთხი, და გარკვეული რაოდენობის ელემენტები აქ, ისევე როგორც ოთხი,
და მე უნდა შერწყმა თითოეული ამ ოთხი , და თითოეული ამ ოთხი, ერთი
მას შემდეგ, რაც სხვა, ასე რომ საბოლოო ჯამში, მე მაქვს რვა ელემენტებს.
ეს იგრძნობა რომ დიდი o N ნაბიჯები?
თუ მაქვს n თითების და თითოეული მათ უნდა გაერთიანდა ადგილი,
რომ არის, კიდევ ერთი N ნაბიჯები.
>> ასე რომ, მართლაც formulaically, ჩვენ შეგვიძლია გამოვხატოთ ამ,
თუმცა ცოტა scarily პირველ რიგში ერთი შეხედვით, მაგრამ ეს არის ის,
რომ captures ზუსტად რომ ლოგიკა.
ქრონომეტრაჟი, ტ ო, თუ n მეტია ან ტოლია 2.
ამ შემთხვევაში, რაღა შემთხვევაში, ტ ო გაყოფილი 2, პლუს T ო იყოფა 2,
პლუს დიდი ო ო, ზოგიერთი ხაზოვანი რიგი ნაბიჯები,
იქნებ ზუსტად n, შესაძლოა, 2-ჯერ n, მაგრამ ეს უხეშად, რათა ო.
ასე რომ, ძალიან, არის თუ როგორ შეუძლია გამოხატოს ამ formulaically.
ახლა თქვენ არ იცით, თუ არ თქვენ ჩაიწერა ეს თქვენი აზრით,
ან ვეძებთ ის, რომ უკან სახელმძღვანელოს, რომელიც
შეიძლება ცოტა შპარგალკა ბოლოს,
მაგრამ ეს, მართლაც, აპირებს მოგვცეს დიდი ო ო ჟურნალი ო,
იმიტომ, რომ არ განმეორდეს, რომ თქვენ ხედავს აქ ეკრანზე,
თუ რეალურად ეს, ერთად უსასრულო რიგი მაგალითები,
ან თქვენ ეს formulaically, თქვენ აკეთებთ ვხედავთ, რომ ეს, იმიტომ, რომ ეს ფორმულა
თავად არის რეკურსიული, ერთად ტ n მეტი რამე მარჯვენა
და ტ ო მეტი მარცხენა, ეს შეიძლება რეალურად იყოს გამოხატული, საბოლოო ჯამში,
როგორც დიდი გადასვლა ო ჟურნალი ო.
თუ არ ვარ დარწმუნებული, რომ ის, ჯარიმა, ახლა, უბრალოდ
იღებს რწმენა, რომ ეს არის ის, მართლაც, რა, რომ განმეორების იწვევს,
მაგრამ ეს არ არის უბრალოდ ცოტა მეტი მათემატიკური მიდგომა ეძებს
ქრონომეტრაჟი შერწყმა დალაგების საფუძველზე მისი pseudocode მარტო.
>> ახლა მოდით ცოტა მსუნთქავი ყველა რომ,
და მიიღოს შევხედოთ გარკვეული ყოფილი სენატორი, რომელიც
შეიძლება ცოტა ნაცნობი, ვინც დაჯდა Google- ის ერიკ
Schmidt, ცოტა ხნის წინ, ინტერვიუში სცენაზე, თვალწინ მთელი bunch
ადამიანი, საუბარი საბოლოოდ შესახებ თემა, რომელიც საკმაოდ ნაცნობი.
მოდით შევხედოთ.
>> ერიკ შმიდტი: ახლა სენატორი, თქვენ აქ Google,
და მე მინდა, ვფიქრობ, პრეზიდენტობის გასაუბრება.
ახლა ეს იმისთვის, რომ მიიღოთ სამუშაოს როგორც პრეზიდენტი.
პრეზიდენტი ობამა: მარჯვენა.
ერიკ შმიდტი: და თქვენ ვაპირებ ამის გაკეთებას [INAUDIBLE] ახლა.
ეს არის ასევე იმისთვის, რომ მიიღოთ სამუშაო Google.
პრეზიდენტი ობამა: მარჯვენა.
>> ერიკ შმიდტი: ჩვენ გვყავს კითხვები და ჩვენ ვთხოვთ ჩვენი კანდიდატების კითხვები,
და ეს ერთი არის Larry შვიმერი.
>> პრეზიდენტი ობამა: OK.
>> ერიკ შმიდტი: რა?
თქვენ ბიჭები ვფიქრობ მე kidding?
ეს უფლება აქ.
რა არის ყველაზე ეფექტური გზა დასალაგებლად მილიონი 32 bit რიცხვებით?
>> პრეზიდენტი ობამა: Well--
ერიკ შმიდტი: ზოგჯერ, იქნებ მე ვწუხვარ, maybe--
პრეზიდენტი ობამა: არა, არა, არა, არა, არა, მე აზრით
ერიკ შმიდტი: ეს არ არის it--
პრეზიდენტი ობამა: მე ვფიქრობ, მე ვფიქრობ, რომ ბუშტი
სახის იქნება არასწორი გზით წასვლა.
ერიკ შმიდტი: კარგით.
ვინ უთხრა, ეს?
OK.
მე არ კომპიუტერულ მეცნიერებათა on--
>> პრეზიდენტი ობამა: ჩვენ გვაქვს მიიღო ჩვენი ჯაშუშების არსებობს.
პროფესორი: ყველა უფლება.
მოდით დატოვება ჩვენს უკან ახლა თეორიული სამყაროში ალგორითმები
ამ ასიმპტოტური ანალიზი მისი, და დაბრუნდეს ზოგიერთი თემა
კვირაში ნულოვანი და ერთი და დაწყების ამოიღონ ზოგიერთი სასწავლო დისკები,
თუ გნებავთ.
ასე, რომ თქვენ ნამდვილად არ მესმის, საბოლოო ჯამში, მიწიდან მდე, რა არის
მიმდინარეობს ქვეშ hood, როდესაც თქვენ წერენ, შედგენა, და შეასრულოს პროგრამები.
შეგახსენებთ, კერძოდ, რომ ეს იყო პირველი C პროგრამის ჩვენ შევხედე,
კანონიკური, მარტივი პროგრამა სახის, შედარებით რომ ვთქვათ,
სადაც, იგი ბეჭდავს, Hello World.
და გავიხსენოთ, რომ მე ვთქვი, რომ ეს პროცესი რომ კოდის გადის
სწორედ ეს არის.
თქვენ თქვენი კოდის, გაივლის ის მეშვეობით შემდგენელი, როგორიც Clang,
და გარეთ მოდის ობიექტის კოდი, რომელიც შეიძლება ასე გამოიყურება, zeros და პირობა
რომ კომპიუტერის CPU, ცენტრალური გადამამუშავებელი ერთეული ან ტვინის,
საბოლოო ჯამში ესმის.
>> გამოდის, რომ ეს არის ის ცოტა გამარტივება,
რომ ჩვენ ახლა პოზიცია აჯავრებენ გარდა
უნდა გვესმოდეს, რა არის მართლაც მიმდინარეობს ქვეშ hood
ყოველ დროს, თქვენ აწარმოებს Clang, ან უფრო ზოგადად,
ყოველ ჯერზე თქვენ პროგრამა, გამოყენებით ჩადება და CF 50 IDE.
კერძოდ, პერსონალის მოსწონს ეს არის პირველი გამომუშავებული,
როდესაც თქვენ პირველად კომპილაციის თქვენი პროგრამა.
სხვა სიტყვებით, როდესაც თქვენ მიიღოს თქვენი კოდის
და კომპილირება, რა არის პირველი მიმდინარეობს outputted მიერ Clang
არის რაღაც ცნობილია, როგორც ასამბლეის კოდი.
და სინამდვილეში, ეს გამოიყურება ზუსტად მოსწონს ეს.
>> მე გაიქცა ბრძანებას ბრძანების ხაზი ადრე.
Clang dash კაპიტალის s hello.c, და ეს ის ფაილი
ჩემთვის მოუწოდა hello.s, შიგნით რაც იყო ზუსტად
ამ შინაარსის, და ცოტა მეტი ზემოთ და ცოტა უფრო ქვემოთ,
მაგრამ მე დააყენა juiciest აქ ეკრანზე.
და თუ ყურადღებით დავაკვირდებით, დავინახავთ, მინიმუმ რამდენიმე ნაცნობი სიტყვა.
ჩვენ გვყავს მთავარი ზედა.
ჩვენ printf ქვემოთ შუა.
ჩვენ ასევე გვაქვს hello მსოფლიოში წარმატებული ო შეთავაზებები ქვემოთ.
>> და ყველაფერი აქ ძალიან დაბალი დონე მითითებები
რომ კომპიუტერის CPU ესმის.
CPU ინსტრუქციას, რომ გადაადგილება მეხსიერება გარშემო, რომ დატვირთვის strings მეხსიერება,
და საბოლოო ჯამში, ბეჭდვითი რამ ეკრანზე.
ახლა რა ხდება, მიუხედავად იმისა, რომ მას შემდეგ, რაც ამ ასამბლეის კოდი გენერირდება?
საბოლოო ჯამში, თქვენ, რა თქმა უნდა, კიდევ წარმოქმნის ობიექტის კოდი.
მაგრამ იმ ნაბიჯებს, რომელიც უნდა ნამდვილად უკვე მიმდინარეობს ქვეშ hood
გამოიყურება უფრო მოსწონს ეს.
კოდის ხდება ასამბლეის კოდი, რომელიც შემდეგ ხდება ობიექტის კოდი,
და ოპერატიული სიტყვა აქ არის ის, რომ, როდესაც თქვენ კომპილაციის თქვენი კოდი,
გარეთ მოდის ასამბლეის კოდი და შემდეგ როდესაც თქვენ შეიკრიბება თქვენი ასამბლეის კოდი,
გარეთ მოდის ობიექტის კოდი.
>> ახლა Clang არის სუპერ დახვეწილი, როგორც ბევრი შემდგენელი,
და ეს იმას ყველა ეს ნაბიჯი ერთად, და ეს სულაც არ
გამომავალი ნებისმიერი შუალედური ფაილი, რომელიც თქვენ კი ვხედავ.
უბრალოდ ადგენს რამ, რომელიც არის ზოგადი ტერმინი, რომელიც
აღწერს ამ პროცესში.
მაგრამ თუ ნამდვილად გსურთ უნდა იყოს კონკრეტული, არსებობს
ბევრი უფრო ხდება იქ.
>> მაგრამ მოდით, ასევე განიხილოს ახლა, რომ თუნდაც რომ სუპერ მარტივი პროგრამა, hello.c,
მოუწოდა ფუნქცია.
მან მოუწოდა printf.
მაგრამ მე არ წერენ printf, რა თქმა უნდა, რომ გააჩნია გ, ასე ვთქვათ.
ეს ფუნქცია შეგახსენებთ, რომ არის განაცხადა სტანდარტული io.h, რომელიც
არის header ფაილი, რომელიც არის თემა, ჩვენ, ფაქტობრივად,
ჩაყვინთვის შევიდა უფრო სიღრმისეული ადრე ხანგრძლივი.
მაგრამ header ფაილი როგორც წესი, თან
მიერ კოდი ფაილი, კოდის ფაილი, ასე რომ ჰგავს არსებობს სტანდარტული io.h.
>> შუალედში წინ, ვინმე, ან ვინმეს, ასევე წერს
ფაილი სახელად სტანდარტული io.c, ამ რომელიც ფაქტობრივი განმარტებები,
ან შესრულება printf, და მტევნების სხვა ფუნქციები,
რეალურად დაწერილია.
ასე რომ, თუ გავითვალისწინებთ, რომ, თუ გავითვალისწინებთ, რომ აქ მარცხენა, hello.c, რომ როდესაც
შედგენილი, გვაძლევს hello.s, მაშინაც კი, თუ Clang არ ადარდებს დაზოგვის ადგილი
ჩვენ ვხედავთ, და რომ ასამბლეის კოდი იღებს შეიკრიბნენ შევიდა hello.o, რომელიც
არის, მართლაც, რა სახელი მაშინვე, როგორც კი თქვენ შედგენა წყაროს
კოდი შევიდა ობიექტის კოდი, მაგრამ არ არის საკმაოდ მზადაა შეასრულოს ის არის,
იმიტომ, რომ კიდევ ერთი ნაბიჯი უნდა მოხდეს, და აქვს
ხდებოდა, რომ ბოლო რამდენიმე კვირის განმავლობაში, ალბათ, არ ვიცი თქვენ.
>> კერძოდ სადღაც ამ CS50 IDE, და ეს,
ძალიან, იქნება ცოტა გამარტივება მომენტში,
არ არის, ან იყო იმ დროს, ფაილი სახელად სტანდარტული io.c,
რომ ვინმე დგება სტანდარტული io.s ან ექვივალენტი,
რომ ვინმე შემდეგ შეიკრიბნენ შევიდა სტანდარტული io.o,
ან გამოდის, შევიდა ოდნავ განსხვავებული ფაილი
ფორმატი, რომელიც შეიძლება ჰქონდეს განსხვავებული ფაილის გაფართოება საერთოდ,
მაგრამ თეორიულად და კონცეპტუალურად, ზუსტად იმ ნაბიჯებს, უნდა მოხდეს გარკვეული ფორმით.
რომელი ვთქვა, რომ ახლა როდესაც მე პროგრამის წერა,
hello.c, რომ ამბობს, Hello World, და მე გამოყენებით სხვისი კოდი
printf, რომელიც იყო ერთხელ დროს, ფაილი სახელად სტანდარტული io.c,
რატომღაც მე უნდა მიიღოს ჩემი ობიექტის კოდი, ჩემი zeros და პირობა,
და რომ პირის ობიექტი კოდი, ან zeros და პირობა,
და როგორღაც დაუკავშირონ მათი ერთად შევიდა ერთი საბოლოო ფაილი, ე.წ. hello, რომ
აქვს ყველა zeros და ვინც ჩემი მთავარი ფუნქცია,
და ყველა zeros და პირობა printf.
>> და მართლაც, ბოლო პროცესი მოუწოდა, აკავშირებს თქვენი ობიექტის კოდი.
გამოშვება, რომელიც არის შესრულებადი ფაილი.
ასე რომ, სამართლიანობა, ზე დღის ბოლოს, არაფერი
შეიცვალა კვირაში ერთი, როდესაც ჩვენ პირველად დაიწყო შედგენა პროგრამები.
მართლაც, ეს ყველაფერი უკვე ხდება ქვეშ hood,
მაგრამ ახლა ჩვენ პოზიცია სადაც ჩვენ შეგვიძლია რეალურად
აჯავრებენ გარდა ამ სხვადასხვა ნაბიჯები.
და მართლაც, ბოლოს დღეს, ჩვენ ჯერ კიდევ
მარცხენა zeros და პირობა, რომელიც ფაქტიურად დიდი segue ახლა
სხვა შესაძლებლობების C, რომ ჩვენ არ ჰქონდა ბერკეტი სავარაუდოდ
დღემდე, რომელიც ცნობილია როგორც bitwise ოპერატორები.
სხვა სიტყვებით, დღემდე, ნებისმიერ დროს ჩვენ განხილული მონაცემების C ან ცვლადები C,
ჩვენ გვქონდა რამ, როგორიცაა chars და მოძრავი და ებზე
და მიისწრაფვის და ორადგილიანი და მოსწონს, მაგრამ ყველა იმ მინიმუმ რვა ბიტი.
ჩვენ არასდროს გაუკეთებია შეძლო მანიპულირება ინდივიდუალური ბიტი,
მიუხედავად იმისა, რომ ინდივიდუალური ცოტა, იცით, შეიძლება წარმოადგენდეს 0 და 1.
ახლა ირკვევა, რომ C, თქვენ შეგიძლიათ მიიღოთ დაშვება ინდივიდუალური ბიტი,
თუ თქვენ იცით, სინტაქსი, , რომლითაც მათ.
>> მოდით შევხედოთ განთავსებულია bitwise ოპერატორები.
ასე რომ, სურათები აქ არის რამდენიმე სიმბოლოები, ჩვენ, სახის, სახის, მინახავს ადრე.
მე ვხედავ ampersand, ვერტიკალური ბარი, და სხვები, ასევე,
და გავიხსენოთ, რომ ampersand ampersand არის რაღაც ჩვენ არ მინახავს ადრე.
ლოგიკური და ოპერატორს, სადაც თქვენ უნდა ორი მათგანი ერთად, ან ლოგიკური ან
ოპერატორი, სადაც თქვენ აქვს ორი ვერტიკალური ბარები.
Bitwise ოპერატორები, რომელიც ჩვენ იხილეთ მოქმედებს ბიტი ინდივიდუალურად,
ისარგებლეთ ერთი ampersand, რომელიც ერთი ვერტიკალური ბარი, caret სიმბოლო
გააჩნია შემდეგი, პატარა tilde, და შემდეგ დატოვა
bracket მარცხენა კვადრატული ფრჩხილი, ან მარჯვენა bracket უფლება bracket.
თითოეული ეს აქვს სხვადასხვა მნიშვნელობა.
>> ფაქტობრივად, მოდით შევხედოთ.
მოდით წავიდეთ ძველი სკოლა დღეს, და გამოყენების სენსორული ეხლა წარსულის,
ცნობილია, როგორც თეთრ დაფაზე.
და ეს თეთრი დაფა აპირებს საშუალებას მოგვცემს
გამოხატოს ზოგიერთი საკმაოდ მარტივი და სიმბოლოები, უფრო სწორად რამდენიმე საკმაოდ მარტივი ფორმულები,
რომ ჩვენ შეგვიძლია მაშინ საბოლოოდ ბერკეტები, რათა
წვდომის ინდივიდუალური ბიტი ფარგლებში C პროგრამა.
სხვა სიტყვებით, მოდით გავაკეთოთ ეს.
მოდით პირველი საუბარი დიდი წუთით ampersand,
რომელიც არის bitwise და ოპერატორს.
სხვა სიტყვებით, ეს არის ოპერატორი, რომელიც საშუალებას იძლევა
ჩემთვის აქვს მარცხენა ცვლადი როგორც წესი, და მარჯვენა ცვლადი,
ან ინდივიდუალური ღირებულება, რომ თუ ჩვენ და მათ ერთად, მაძლევს საბოლოო შედეგი.
ასე რომ, რას ვგულისხმობ?
იმ შემთხვევაში, თუ პროგრამა, თქვენ გაქვთ ცვლადი რომ მაღაზიებში ერთი ამ ღირებულებების,
ან მოდით შეინახოს იგი მარტივი, და მხოლოდ წერენ გარეთ zeros და პირობა ინდივიდუალურად,
აქ არის თუ როგორ ampersand ოპერატორი მუშაობს.
0 ampersand 0 აპირებს უდრის 0.
ახლა რატომ არის, რომ?
>> ეს ძალიან ჰგავს ლოგიკური გამონათქვამები,
რომ ჩვენ განიხილეს დღემდე.
თუ ფიქრობთ, რომ მას შემდეგ, რაც ყველა, 0 არის ყალბი, 0 არის ყალბი, ყალბი და ცრუ
არის, როგორც ჩვენ განვიხილეთ ლოგიკურად, ასევე ყალბი.
ასე რომ, ჩვენ კიდევ 0 აქაც.
თუ თქვენ მიიღოს 0 ampersand 1, ისე, რომ, ძალიან,
იქნება 0, რადგან ამ მარცხენა გამოხატვის უნდა იყოს ჭეშმარიტი ან 1,
ეს უნდა იყოს ჭეშმარიტი და მართალია.
მაგრამ აქ ჩვენ გვაქვს ყალბი და ჭეშმარიტი, ან 0 და 1.
ახლა, თუ ჩვენ გვაქვს 1 ampersand 0, რომ, ძალიან, იქნება 0,
და თუ ჩვენ 1 ampersand 1, საბოლოოდ არ გვაქვს 1 bit.
ასე რომ, სხვა სიტყვებით რომ ვთქვათ, ჩვენ არ ვაკეთებთ არაფერი საინტერესო ამ ოპერატორს
უბრალოდ არ არის, ამ ampersand ოპერატორი.
ეს არის bitwise და ოპერატორს.
მაგრამ ეს ინგრედიენტები მეშვეობით, რომელიც ჩვენ შეგვიძლია გავაკეთოთ
საინტერესო რამ, როგორც ჩვენ მალე.
>> ახლა მოდით შევხედოთ მხოლოდ ერთი ვერტიკალური ბარი მეტი აქ უფლება.
თუ მე მაქვს 0 ცოტა და მე ან ის, რომ bitwise
ან ოპერატორის, მეორე 0 bit, რომ აპირებს მომეცი 0.
თუ მე ავიღებ 0 bit და ან ეს 1 bit, მაშინ მე ვაპირებ, რომ მიიღოთ 1.
და სინამდვილეში, მხოლოდ სიწმინდე, ნება მომეცით დაბრუნდეს,
ისე, რომ ჩემი ვერტიკალური ბარები არ ცდება 1 ს.
მოდი გადავწერ ყველა ჩემი 1 ცოტა მეტი
ნათლად, ისე, რომ ჩვენ მომავალ ვხედავ, თუ აქვს 1 ან 0, რომელიც იქნება 1,
და თუ მე მაქვს 1 ან 1, რომ ძალიან, იქნება 1.
ასე რომ თქვენ ხედავთ, ლოგიკურად რომ OR ოპერატორი იქცევა განსხვავებულად.
ეს მაძლევს 0 ან 0 მაძლევს 0, მაგრამ ყველა სხვა კომბინაცია მაძლევს 1.
ასე რომ, სანამ მე ერთი 1- ფორმულა, შედეგი იქნება 1.
>> ამის საპირისპიროდ ერთად და ოპერატორი, ampersand,
მხოლოდ იმ შემთხვევაში, მე მაქვს ორი 1 წელს განტოლება, შემიძლია რეალურად მიიღოთ 1 out.
ახლა არის რამდენიმე სხვა ოპერატორები, ასევე.
ერთ-ერთი მათგანი არის ცოტა უფრო ჩართული.
ნება მომეცით წავიდეთ წინ და წაშლას ამ გასათავისუფლებლად მდე გარკვეული სივრცე.
და მოდით შევხედოთ caret სიმბოლო, მხოლოდ ერთი წუთით.
ეს არის, როგორც წესი, ხასიათი შეგიძლიათ ჩაწეროთ
თქვენს კლავიატურაზე ჩატარების Shift და მაშინ ერთ ნომრები atop თქვენი აშშ
კლავიატურაზე.
>> ასე რომ, ეს არის ექსკლუზიური ან ოპერატორის, განსაკუთრებული ან.
ასე რომ, ჩვენ უბრალოდ დაინახა ან ოპერატორის.
ეს არის განსაკუთრებული ან ოპერატორს.
რა არის რეალურად განსხვავება?
ისე მოდით შევჩერდეთ ფორმულა, და გამოიყენოს ეს ინგრედიენტები საბოლოოდ.
0 XOR 0.
მე ვაპირებ ვთქვა ყოველთვის 0.
ეს არის განმარტება XOR.
0 XOR 1 იქნება 1.
1 XOR 0 იქნება 1, და 1 XOR 1 იქნება?
არასწორი?
ან მარჯვენა?
მე არ ვიცი.
0.
ახლა, რა ხდება აქ?
ისე ვიფიქროთ სახელი ამ ოპერატორს.
ექსკლუზიური ან, ისე, სახელი, სახის, ვარაუდობს,
პასუხი მხოლოდ იქნება 1 თუ საშუალებებით არის ექსკლუზიური,
მხოლოდ განსხვავებული.
ასე რომ, აქ საშუალებებით არიან იგივე, ასე რომ გამომავალი 0.
აქ საშუალებებით არიან იგივე, ასე რომ გამომავალი 0.
აქ არის შედეგები სხვადასხვა, მათ ექსკლუზიური და ასე გამომავალი 1.
ასე რომ, ეს ძალიან ჰგავს და, ეს ძალიან ჰგავს,
ან პირიქით, ეს ძალიან ჰგავს OR, მაგრამ მხოლოდ ექსკლუზიური გზა.
ეს ერთი აღარ არის 1, იმიტომ, რომ ჩვენ გვაქვს ორი 1-ის,
და არა მხოლოდ, მხოლოდ ერთი მათგანი.
ყველა უფლება.
რაც შეეხება სხვები?
ისე tilde, იმავდროულად, არის რეალურად ლამაზი და მარტივი, საბედნიეროდ.
და ეს არის unary ოპერატორი, რაც იმას ნიშნავს,
ის გამოიყენება მხოლოდ ერთი input, ერთი operand, ასე ვთქვათ.
არ მარცხენა და მარჯვენა.
სხვა სიტყვებით, თუ თქვენ მიიღოს tilde of 0 პასუხი იქნება, პირიქით.
და თუ tilde of 1, პასუხი არ იქნება, პირიქით.
ასე რომ, tilde ოპერატორი გზა უარყოფს ცოტა,
ან flipping ცოტა 0 1 ან 1: 0.
>> და რომ ტოვებს საბოლოოდ მხოლოდ ორი საბოლოო ოპერატორები,
ე.წ. მარცხენა ცვლა, და ე.წ. უფლება ცვლის ოპერატორი.
მოდით შევხედოთ, თუ როგორ იმ სამუშაოს.
მარცხენა Shift ოპერატორი, წერილობითი ორი კუთხე ფრჩხილებში, როგორც, რომ,
მოქმედებს შემდეგნაირად.
თუ ჩემი შეყვანის, ან ჩემი operand, რომ მარცხნივ ცვლის ოპერატორი საკმაოდ უბრალოდ 1.
შემდეგ მე და ვუთხრა კომპიუტერი მარცხენა ცვლა, რომ 1, ამბობენ, შვიდი ადგილებში,
შედეგი ის არის, თითქოს მე მიიღოს, რომ 1 და გადატანა
შვიდი ადგილებში მეტი მარცხენა და ჩვეულებრივ,
ჩვენ ვაპირებთ, უნდა ვივარაუდოთ, რომ სივრცეში მარჯვნივ
იქნება დადიოდა ერთად zeros.
სხვა სიტყვებით, 1 მარცხენა ცვლა 7 აპირებს მაძლევს, რომ 1, მოჰყვა 1, 2, 3,
4, 5, 6, 7 zeros.
ისე, ის საშუალებას გაძლევთ მიიღოს მცირე რაოდენობის 1,
და ნათლად, რათა ის უფრო ბევრად, ბევრად უფრო დიდი, ამ გზით,
მაგრამ ჩვენ რეალურად აპირებს ვხედავ უფრო ჭკვიანი მიდგომების ეს
ნაცვლად, ისევე,
>> ყველა უფლება.
ეს არის ის, კვირაში სამი.
ჩვენ ვნახავთ თქვენ მომავალი დრო.
ეს იყო CS50.
>> [მუსიკის დაკვრა]
>> დინამიკები 1: ის იმყოფებოდა snack ბარი ჭამა ცხელი fudge sundae.
მას ჰქონდა ის მთელი მისი სახე.
ის ეცვა, რომ შოკოლადი, როგორც წვერი
დინამიკები 2: რას აკეთებთ?
დინამიკები 3: Hmmm?
რა არის ეს?
>> დინამიკები 2: იცით თუ უბრალოდ ორმაგი დიპლომატიური?
თქვენ ორმაგი dipped ჩიპი.
დინამიკები 3: მაპატიეთ.
დინამიკები 2: თქვენ dipped ჩიპი, თქვენ აიღო bite, და თქვენ dipped ერთხელ.
დინამიკები 3:
დინამიკები 2: ასე რომ, როგორიცაა აყენებს მთელი პირით უფლება Dip.
მომავალი დრო თქვენ მიიღოს ჩიპი, მხოლოდ დიპლომატიური ერთხელ, და დასრულდება იგი.
>> დინამიკები 3: თქვენ იცით, რა, დენ?
თქვენ ამოთხრა ისე, რომ გსურთ ამოთხრა.
მე დიპლომატიური გზა, რომ მინდა ამოთხრა.