[Powered by Google Translate] [ნაწილი 3 - უფრო კომფორტული] [Rob Bowden - ჰარვარდის უნივერსიტეტი] 

[ეს არის CS50. - CS50.TV] 

ასე რომ პირველი კითხვა არის უცნაურად ფორმულირებული. GDB გაძლევთ "გამართვის" პროგრამით, მაგრამ, უფრო კონკრეტულად, რას მოგცემთ გავაკეთოთ? მე პასუხი, რომ ერთი, და მე არ ვიცი რა ზუსტად მოსალოდნელია, ამიტომ მე გამოცნობა ეს რაღაც გასწვრივ ხაზი იგი საშუალებას გაძლევთ ეტაპობრივად გავლა პროგრამის, ურთიერთქმედება ის, ენის ცვლადები, გავაკეთოთ ეს ყველაფერი - ძირითადად მთლიანად აკონტროლებენ აღსრულების პროგრამა და გაეცნონ ნებისმიერი ნაწილი აღსრულების პროგრამა. ასე რომ იმ თვისებების მოგცემთ გამართვის რამ. Okay. რატომ ბინარული ძებნის მოითხოვს, რომ მასივი იყოს დახარისხებული? ვის უნდა უპასუხოს, რომ? [სტუდენტი], რადგან ის არ იმუშავებს თუ ეს არ დახარისხებული. >> Yeah. [სიცილის] თუ ეს არ დახარისხებული, მაშინ შეუძლებელია გაყოფილი ის ნახევარზე და ვიცით, რომ ყველაფერი მარცხენა ნაკლებია და ყველაფერი სწორი მეტია შუა ღირებულება. ასე რომ ის უნდა დახარისხებული. Okay. რატომ არის ბუშტი sort in O of n კვადრატში? ვინმეს პირველი მინდა ძალიან სწრაფი მაღალი დონის მიმოხილვა რა ბუშტი დალაგების არის? [სტუდენტი] თქვენ ძირითადად გავლა თითოეულ ელემენტს და თქვენ შეამოწმოთ პირველი რამდენიმე ელემენტებს. თუ ისინი ვერ გამოვიდა, სადაც თქვენ სვოპ მათ, მაშინ შეამოწმოთ მომდევნო რამდენიმე ელემენტები და ასე შემდეგ. როდესაც თქვენ მივაღწიოთ ბოლოს, მაშინ თქვენ იცით, რომ ყველაზე დიდი ელემენტს განთავსებულია დასასრულს, ასე რომ თქვენ იგნორირება, რომ ერთი მაშინ გააგრძელოს გადის, და ყოველ ჯერზე თქვენ უნდა შეამოწმოთ ერთი ნაკლებად ელემენტს სანამ არ მიიღოს ცვლილებები არ. >> Yeah. ეს მოუწოდა bubble sort, რადგან თუ თქვენ Flip მასივი თავის მხრივ ამიტომ up და down, ვერტიკალური, მაშინ დიდი ღირებულებები ჩაიძიროს ბოლოში და პატარა ღირებულებები ბუშტი მდე დაბრუნება. ასე მას თავისი სახელი. და ჰო, უბრალოდ გავლა. თქვენ გაქვთ გადის მასივი, შევცვალე უფრო დიდი ღირებულება მიიღოს უდიდესი ღირებულებები ბოლოში. 

რატომ არის O of n კვადრატში? პირველი, ჯერ არავის მინდა ვთქვა, რატომ არის O of n კვადრატში? [სტუდენტი] გამო თითოეული გაუშვით მიდის N ჯერ. თქვენ შეგიძლიათ მხოლოდ დარწმუნდით, რომ თქვენ აღებული უმსხვილესი ელემენტს ყველა გზა down, მაშინ თქვენ უნდა გავიმეოროთ, რომ რაც შეიძლება ბევრი ელემენტები. >> Yeah. ასე რომ გაითვალისწინეთ რა დიდი O ნიშნავს და რა დიდი Omega საშუალებით. დიდი O ჰგავს ზედა შეკრული, თუ როგორ ნელა მას შეუძლია რეალურად აწარმოებს. ასე განაცხადა მისი O of n კვადრატში, ეს არ არის O of n ანდა იგი შეძლებს აწარმოებს წელს ხაზოვანი დროს, მაგრამ ეს O of n cubed რადგან ეს ესაზღვრება O of n cubed. თუ ეს ესაზღვრება O of n კვადრატში, მაშინ ის ესაზღვრება ასევე N cubed. სწორედ ამიტომ, n კვადრატში, და აბსოლუტური უარეს შემთხვევაში მას არ შეუძლია უკეთესად N კვადრატში, რის გამოც ის O მიერ ენ კვადრატში. ასე, რომ ნახოთ უმნიშვნელო მათემატიკის როგორ საქმე აღმოჩნდება N კვადრატში, თუ ჩვენ გვაქვს ხუთი რამ ჩვენს სიაში, პირველად რამდენი სვოპების შეგვეძლო პოტენციურად მოგიწევთ რათა მიიღოთ ამ? მოდით რეალურად მხოლოდ - რამდენი სვოპების მივდივართ ჰქონდეს, რათა პირველ პერსპექტივაში of bubble sort მეშვეობით მასივი? [სტუდენტი] n - 1. >> Yeah. 

თუ არსებობს 5 ელემენტები, ჩვენ ვაპირებთ მოგიწევთ n - 1. მერე მეორე რამდენი სვოპების მივდივართ რომ უნდა გააკეთოთ? [სტუდენტი] N - 2. >> Yeah. და მესამე იქნება N - 3, ხოლო შემდეგ მოხერხებულობის მე დაწერს ბოლო ორი როგორც მაშინ ჩვენ ვაპირებთ მოგიწევთ 2 გაცვლებს და 1 swap. ვფიქრობ ბოლო ერთი შეიძლება იყოს ან არ რეალურად უნდა მოხდეს. არის თუ არა swap? მე არ ვიცი. ასე რომ ეს არის სულ რაოდენობით გაცვლებს ან თუნდაც შედარებები თქვენ უნდა გააკეთოთ. მაშინაც კი, თუ თქვენ არ სვოპ, თქვენ კვლავ უნდა შეადაროთ ღირებულებებს. ასე რომ N - 1 შედარებები პირველ პერსპექტივაში მეშვეობით მასივი. თუ თქვენ rearrange ეს ყველაფერი, მოდით რეალურად ხდის, ექვსი რამ ასე რამ დააწყობს up ლამაზად, და მაშინ მე გავაკეთებ 3, 2, 1. ასე რომ მხოლოდ rearranging ეს თანხები, ჩვენ გვინდა, რომ რამდენი შედარებები ჩვენ მთელ ალგორითმი. ასე რომ, თუ ჩვენ მოუტანს ეს ბიჭები ქვემოთ აქ, მაშინ ჩვენ ჯერ კიდევ მხოლოდ შემაჯამებელი თუმცა ბევრი შედარებები იყო. მაგრამ თუ ჩვენ მთლიანობაში ეს და ჩვენ მთლიანობაში ეს და ჩვენ მთლიანობაში ეს, მაინც იგივე პრობლემა. ჩვენ უბრალოდ მთლიანობაში იმ კონკრეტულ ჯგუფებს. 

ახლა ჩვენ შემაჯამებელი 3 N-ს. ეს არ არის მხოლოდ 3 N-ს. ის ყოველთვის იქნება N / 2 N-ს. ასე რომ აქ ჩვენ ემართება აქვს 6. თუ ჩვენ გვქონდა 10 რამ, მაშინ ჩვენ შეგვიძლია ამის გაკეთება დაჯგუფება, 5 სხვადასხვა წყვილი რამ და დასრულდება up ერთად N + N + N + N + N. ასე რომ თქვენ ყოველთვის მიიღებთ N / 2 N-ს, და ა.შ. ეს ჩვენ jot იგი აღმოჩნდება N კვადრატში / 2. და ა.შ. მიუხედავად იმისა, რომ ეს ფაქტორი ნახევარი, რაც ხდება მოსვლა გამო იმისა, რომ მეშვეობით თითოეულ iteration მეტი მასივი შევადარებთ 1 ნაკლები ასე რომ, თუ როგორ მივიღებთ დაახლოებით 2, მაგრამ იგი მაინც n კვადრატში. ჩვენ არ აინტერესებს მუდმივი ფაქტორი ნახევარში. ასე რომ ბევრი დიდი O პერსონალის მოსწონს ეს ეყრდნობა მხოლოდ სახის აკეთებს ამ სახის მათემატიკის, აკეთებს არითმეტიკული თანხები და გეომეტრიული სერიის პერსონალის, მაგრამ მათი უმრავლესობა ამ კურსში არიან საკმაოდ მარტივია. Okay. რატომ არის Insertion sort in Omega of N? რას ნიშნავს omega? [ორი სტუდენტი საუბრობდა ერთხელ - გაუგებარია] >> Yeah. Omega შეგიძლიათ წარმოიდგინოთ, რომ როგორც ქვედა შეკრული. 

ასე რომ რაც არ უნდა ეფექტური თქვენი Insertion დახარისხების ალგორითმი არის, მიუხედავად სიაში რომ გადავიდა, მას ყოველთვის აქვს შედარება მინიმუმ N რამ ან ის iterate მეტი N რამ. რატომ არის, რომ? [სტუდენტი] რადგან თუ სიაში უკვე დახარისხებული, მაშინ მეშვეობით პირველი iteration თქვენ შეგიძლიათ მხოლოდ გარანტიას, რომ პირველივე ელემენტს არის მაინც, და მეორე iteration შეგიძლიათ ერთადერთი გარანტია პირველი ორი რადგან არ ვიცით, რომ დანარჩენ სია დალაგებულია. >> Yeah. თუ გაივლის სრულიად დახარისხებული სია, სულ ცოტა, თქვენ უნდა წავიდეთ ყველა ელემენტები დაინახოს, რომ არაფერი უნდა იყოს გადავიდა გარშემო. ამიტომ გარდაცვალება სიაში და ამბობდა oh, ეს უკვე დახარისხებული, ეს შეუძლებელია, იცოდეთ ეს დახარისხებული სანამ თქვენ შეამოწმოთ თითოეულ ელემენტს დაინახოს, რომ ისინი დახარისხებული მიზნით. ასე რომ ქვედა შეკრული on Insertion დალაგების არის ომეგა of n. რა უარეს შემთხვევაში გაშვებული დრო შერწყმა დახარისხების, უარეს შემთხვევაში ყოფნა დიდი O ერთხელ? ასე რომ, უარეს შემთხვევაში სცენარი, თუ როგორ ამჯამად შერწყმა დალაგების აწარმოებს? [სტუდენტი] N შესვლა n. >> Yeah. უსწრაფესი ზოგადი დახარისხება ალგორითმები N შესვლა n. თქვენ არ შეგიძლიათ უკეთესად. 

არსებობს განსაკუთრებულ შემთხვევებში და, თუ ჩვენ გვაქვს დრო დღეს - მაგრამ ჩვენ ალბათ won't - ჩვენ ვხედავდით ერთი რომ აკეთებს უკეთესად N შესვლა n. მაგრამ ზოგადად შემთხვევაში, თქვენ ვერ უკეთესად N შესვლა n. და შერწყმის დალაგება ხდება იყოს ერთი თქვენ უნდა იცოდეს, ამ თქმა, რომ არის N შესვლა n. და ა.შ. ჩვენ რეალურად უნდა განხორციელების, რომ დღეს. და ბოლოს, არა უმეტეს სამი სასჯელს, რამდენად შეესაბამება შერჩევის დალაგების მუშაობს? ამჯამად ვინმე გვინდა პასუხის გაცემა, და მე დათვალეთ სასჯელი რადგან თუ მეტი 3 - ვინმეს გახსოვთ შერჩევის დალაგება? შერჩევა დალაგების ჩვეულებრივ საკმაოდ ადვილად დასამახსოვრებელი მხოლოდ სახელი. თქვენ უბრალოდ iterate მეტი მასივი, იპოვეთ რასაც უდიდესი მნიშვნელობა არის თუ პატარა - რასაც რათა თქვენ დახარისხება სისტემაში ასე ვთქვათ ჩვენ დახარისხება საწყისი პატარა რომ უდიდესი. თქვენ iterate მეტი მასივი, ეძებს რასაც მინიმალური ელემენტი, ამოირჩიეთ, ხოლო შემდეგ მხოლოდ სვოპ ის რაც პირველ რიგში. და მერე მეორე უვლის მასივი, გადახედეთ მინიმალური ელემენტს ერთხელ, ამოირჩიეთ, შემდეგ სვოპ იგი რა მეორე ადგილი დაიკავეს. ჩვენ უბრალოდ კრეფა და ვირჩევთ მინიმალური ღირებულებები და ჩასმა მათთვის წინაშე მასივი სანამ ეს დახარისხებული. კითხვები რომ? 

ეს აუცილებლად გამოჩნდება ფორმები თქვენ უნდა შეავსონ როცა თქვენ წარდგენის pset. იმ ძირითადად პასუხი იმ. Okay, ასე არის კოდირების პრობლემები. მე უკვე გააძევეს მეტი ელ - ერთი ვინმე არ მიიღოთ, რომ წერილი? Okay. მე უკვე გააძევეს მეტი ელექტრონული სივრცე, როგორიც ჩვენ ვაპირებთ იყოს გამოყენებით, და თუ თქვენ დააჭირეთ ჩემი სახელი - ასე ვფიქრობ მე ვაპირებ იყოს ბოლოში გამო უკან r - მაგრამ თუ თქვენ დააჭირეთ ჩემი სახელი დაინახავთ 2 ვერსიებს. ცვლილებათა 1 იქნება მე უკვე გადაწერილი და pasted კოდი შევიდა სივრცეები ამისთვის ძებნა რაც თქვენ ვაპირებთ უნდა განახორციელოს. და სარევიზიო 2 იქნება დალაგების რამ, რომ ჩვენ განახორციელოს ამის შემდეგ. ამიტომ დააკლიკეთ ჩემი ცვლილებათა 1 და მუშაობა იქიდან. და ახლა ჩვენ გვინდა განვახორციელოთ ორობითი ძებნა. 

ვინმეს გვინდა უბრალოდ მისცეს pseudocode მაღალი დონის განმარტება რასაც ჩვენ ვაპირებთ უნდა გავაკეთოთ ძებნის? Yeah. [სტუდენტი] თქვენ უბრალოდ მიიღოს შუა array და ვხედავ თუ თქვენ მას ეძებს ნაკლებია ან მეტია. და თუ ის ნაკლებია, მიდიხარ ნახევარი რომ ნაკლებად, და თუ ეს უფრო, მიდიხარ ნახევარი, რომ უფრო და თქვენ გავიმეორო, რომ სანამ არ უბრალოდ ერთი რამ. [Bowden] Yeah. გაითვალისწინეთ, რომ ჩვენი ნომრები მასივი უკვე დახარისხებული, და ა.შ. ეს იმას ნიშნავს, რომ ჩვენ შეგვიძლია ისარგებლოს და ჩვენ შეიძლება პირველი ჩეკი, okay, ვეძებ ნომერი 50. ასე, რომ შეიძლება წასვლას ახლო. ახლო რთულია განსაზღვრა, როდესაც ეს კი რაოდენობის ნივთები, მაგრამ მოდით უბრალოდ, ვამბობთ ჩვენ ყოველთვის truncate შუა. ასე რომ აქ გვაქვს 8 რამ, ასე ახლო იქნებოდა 16. ვეძებ 50, ისე 50 მეტია 16. ახლა შემიძლია ძირითადად მკურნალობა ჩემი მასივს როგორც ამ ელემენტებს. შემიძლია გადაყარეთ ყველაფერი 16 ზე. ახლა ჩემი მასივი მხოლოდ ამ 4 ელემენტები, და ვიმეორებ. ასეა, მაშინ მინდა მოვძებნოთ ახლო ისევ, რომელიც იქნება 42. 42 ნაკლებია, ვიდრე 50, ასე, რომ შეიძლება გადაყარეთ ამ ორი ელემენტები. ეს არის ჩემი დარჩენილი მასივი. მე ვაპირებ მოვძებნოთ ახლო ერთხელ. ვფიქრობ 50 იყო ცუდი მაგალითი, რადგან მე ყოველთვის სროლა მოშორებით რამ მარცხენა მაგრამ ამავე ღონისძიების, თუ ვეძებ რაღაც და ეს ნაკლები ელემენტს მე გაკეთებული ეძებს, მაშინ მე ვაპირებ გადაყარეთ ყველაფერი უფლება. ახლა ჩვენ გვჭირდება, რომ განხორციელდეს, რომ. გაითვალისწინეთ, რომ ჩვენ უნდა გაიაროს ზომის. ჩვენ შეგვიძლია ასევე არ უნდა მყარი კოდი ზომა. ასე რომ, თუ ჩვენ დავაღწიოთ რომ # define - Okay. როგორ შემიძლია ლამაზად გაერკვნენ, რა ზომის ციფრები მასივი გაკეთებული არის? 

რამდენი ელემენტები არიან ნომრები მასივი? [სტუდენტი] ნომრები, ფრჩხილებში,. სიგრძე? [Bowden], რომ არ არსებობს C. გჭირდებათ. სიგრძე. კოლექტორები არ აქვს თვისებები, ასე რომ არ არსებობს სიგრძე ქონება მასივი რომ მხოლოდ მოგცემთ თუმცა ხანგრძლივი ხდება, რომ იყოს. [სტუდენტი] რამდენად ბევრი მეხსიერების მას და ყოფს მიერ რამდენად - >> Yeah. ასე როგორ შეიძლება ჩვენ ვხედავთ, თუ რამდენი მეხსიერება მას? >> [სტუდენტი] Sizeof. >> Yeah, sizeof. Sizeof არის ოპერატორი, რომ აპირებს დაბრუნებას ზომის ციფრები მასივი. და ეს იქნება თუმცა ბევრი რიცხვებით არსებობს ჯერ ზომა რიცხვი რადგან ეს არის ის, თუ რამდენად მეხსიერების სინამდვილეში მიღება. ასე რომ, თუ მინდა ხმების რამ მასივი, მაშინ მე ვაპირებ მინდა გაყავით მიერ ზომა რიცხვი. Okay. ასე რომ, რომელიც საშუალებას ჩემთვის გაივლის ზომის აქ. რატომაა გავლა ზომის ყველა? რატომ არ შემიძლია უბრალოდ აქ int size = sizeof (haystack) / sizeof (int)? რატომ ამ არ იმუშავებს? [სტუდენტი] ეს არ გლობალური ცვლადი. [Bowden] Haystack არსებობს და ჩვენ გადადის ნომრები haystack, და ეს არის ერთგვარი foreshadowing რა მოვა. Yeah. [სტუდენტი] Haystack მხოლოდ მინიშნება მას, ასე რომ დაბრუნდნენ რამდენად დიდი რომ მინიშნება არის. Yeah. მე ეჭვი ლექცია რომ თქვენ ვხედავთ დასტის ჯერჯერობით ნამდვილად, არა? ჩვენ უბრალოდ ლაპარაკობენ ამის შესახებ. ამიტომ დასტის არის სადაც ყველა თქვენი ცვლადები ვაპირებთ ინახება. 

ნებისმიერი მეხსიერების რომ გამოყოფილი ადგილობრივი ცვლადები ხდება დასტის, და თითოეული ფუნქციის იღებს საკუთარი სივრცე დასტის, საკუთარი დასტის ჩარჩო არის რასაც ის მოუწოდა. ასე რომ მთავარ აქვს თავისი დასტის ჩარჩო, და შიგნით რომ აპირებს არსებობს ამ ნომრებზე მასივი, და ეს იქნება საქართველოს ზომა sizeof (ციფრები). ის აპირებს ზომის ციფრები იყოფა ზომის ელემენტები, მაგრამ, რომ ყველა ცხოვრების განმავლობაში ძირითად ს დასტის ჩარჩო. როდესაც ჩვენ მოვუწოდებთ ძებნა, ძიება იღებს საკუთარი დასტის ჩარჩო, საკუთარი სივრცის შესანახად ყველა მისი ადგილობრივი ცვლადები. მაგრამ ეს არგუმენტები - ასე haystack არ არის ასლის მთელი მასივი. ჩვენ არ გაივლის მთელ მასივს როგორც ასლი შევიდა ძებნა. უბრალოდ გადის მინიშნება, რომ მასივი. ასე ძებნა შეუძლიათ ამ ნომრებზე მეშვეობით მითითება. დღემდე წვდომის რამ, რომ იცხოვრონ შიგნით ძირითადი მისი დასტის ჩარჩო, მაგრამ ძირითადად, როცა ჩვენ ვიღებთ, რათა მითითებები, რომელიც უნდა იყოს სულ მალე, ეს რა მითითებები. მითითებები მხოლოდ მითითება რამ, და შეგიძლიათ გამოიყენოთ პოინტერები წვდომისათვის რამ რომ მსოფლიოს სხვა რამ 'დასტის ფარგლებში. ასე რომ, მიუხედავად იმისა, ნომრები არის ადგილობრივი მთავარ, ჩვენ მაინც ვებგვერდზე მეშვეობით ამ მაჩვენებელმა. მაგრამ რადგან ეს მხოლოდ კურსორი და უბრალოდ მინიშნება, sizeof (haystack) უბრალოდ ბრუნდება ზომა მინიშნება თავად. ეს არ დააბრუნებს ზომა რამ ეს მიუთითებს. ეს არ დააბრუნებს ფაქტობრივი ზომის ციფრები. და ასე რომ, ეს არ იმუშავებს, როგორც ჩვენ გვსურს. 

კითხვები რომ? პოინტერები იქნება გადაიზარდა მნიშვნელოვნად მეტი გორის დეტალურად კვირის მოსვლა. და სწორედ ამიტომ ბევრი რამ, რომ ხედავთ, ყველაზე ძებნა რამ ან დალაგება რამ, ისინი თითქმის ყველა აპირებს უნდა მიიღოს ფაქტობრივი ზომა მასივი, რადგან C, არ ვიცით, რა ზომის მასივი. თქვენ უნდა ხელით მსგავ სისტემაში და ვერ ხელით გაივლის მთელ მასივი, რადგან თქვენ მხოლოდ გადადის მინიშნება და მას არ შეუძლია მიიღოს ზომა საწყისი მითითება. Okay. ახლა ჩვენ გვინდა განვახორციელოთ რა განემარტა ადრე. შეგიძლიათ იმუშაოთ მასზე ერთი წუთით, და თქვენ არ ფიქრი მისაღებად ყველაფერი შესანიშნავად 100% მუშაობს. უბრალოდ წერენ up ნახევარში pseudocode თუ როგორ ფიქრობთ, უნდა იმუშაოს. Okay. არ უნდა იყოს მთლიანად გაკეთდეს ამ ამჟამად. მაგრამ ჯერ არავის გრძნობდნენ თავს კომფორტულად რაც მათ აქამდე, მოსწონს რაღაც შეგვიძლია ვიმუშაოთ ერთად? ვინმეს გვინდა მოხალისე? თორემ შემთხვევით აირჩიოთ. იგი არ უნდა იყოს უფლება ნებისმიერი ზომის მაგრამ შეგვიძლია ცვლილებები შევიდა სამუშაო სახელმწიფო. [სტუდენტი] რა თქმა უნდა. >> Okay. ასე რომ შეგიძლიათ შეინახოთ გადასინჯვის დაწკაპვით პატარა Save ხატი. თქვენ Ramya, არა? >> [სტუდენტი] Yeah. >> [Bowden] Okay. ახლა შემიძლია თქვენს გადასინჯვის და ყველას შეუძლია დახევის up გადასინჯვის. და აქ ჩვენ გვაქვს - Okay. ამიტომ Ramya წავიდა ერთად რეკურსიული გამოსავალი, რომელიც ნამდვილად სწორი გადაწყვეტა. არსებობს ორი გზა შეგიძლიათ გააკეთოთ ეს პრობლემა. თქვენ შეგიძლიათ ან გავაკეთებთ iteratively ან რეკურსიული. ყველაზე პრობლემებს თქვენ ექმნებათ, რომ შეიძლება გაკეთდეს რეკურსიული ასევე შეიძლება გაკეთდეს iteratively. ასე რომ აქ ჩვენ გავაკეთეთ ეს რეკურსიული. 

ამჯამად ვინმე გვინდა განვსაზღვროთ, თუ რას ნიშნავს, რათა ფუნქცია რეკურსიული? [სტუდენტი] როდესაც თქვენ გაქვთ ფუნქცია მოვუწოდებთ თავად და შემდეგ მოვუწოდებთ თავად სანამ გამოდის ჭეშმარიტი და მართალია. >> Yeah. რეკურსიული ფუნქცია მხოლოდ ფუნქცია, რომელიც მოუწოდებს თავად. არსებობს სამი დიდი რამ, რომ რეკურსიული ფუნქცია უნდა ჰქონდეს. პირველი აშკარად, ის მოუწოდებს თავად. მეორე ბაზის შემთხვევაში. ასე რომ რაღაც მომენტში ფუნქცია სჭირდება შეჩერება მოუწოდებდა თავად, და ეს რა ბაზა შემთხვევაში არის. ასე რომ აქ ჩვენ ვიცით, რომ ჩვენ უნდა შეწყვიტოს, ჩვენ უარი უნდა თქვას ჩვენს ძებნა როდესაც დაწყება შეადგენს ბოლოს - და ჩვენ წავიდეთ მეტი რა უნდა ნიშნავდეს ეს. მაგრამ საბოლოოდ, ბოლო რაც მნიშვნელოვანია რეკურსიული ფუნქციების: ფუნქციები უნდა როგორღაც მიახლოება ბაზის შემთხვევაში. Like თუ თქვენ არ რეალურად განახლებაზე არაფერი გამოვა მეორე რეკურსიული ზარი, თუ თქვენ სიტყვასიტყვით უბრალოდ მოუწოდებდა ფუნქციის კვლავ იგივე არგუმენტები და არ გლობალური ცვლადები შეიცვალა ან არაფერი, თქვენ არასოდეს აღწევს ბაზის შემთხვევაში, ამ შემთხვევაში რომ ცუდია. ეს იქნება უსასრულო უკან და დასტის overflow. მაგრამ აქ ჩვენ ვხედავთ, რომ განახლება ხდება, რადგან ჩვენ განახლებაზე დაიწყებს + ბოლომდე / 2, ჩვენ განახლებაზე ბოლოს არგუმენტი აქ, ჩვენ განახლებაზე დაწყება არგუმენტი აქ. ასე რომ ყველა რეკურსიული მოუწოდებს ჩვენ განახლებაზე რაღაც. Okay. გნებავთ ფეხით us საშუალებით თქვენი გამოსავალი? >> დარწმუნებული. მე გამოყენებით SearchHelp ისე, რომ ყოველ ჯერზე მე ამ ფუნქციის ზარის მაქვს დაწყების სადაც მე ვეძებ მასივში და ბოლოს სადაც მე დიდი იმედით მასივი. 

ყოველ ნაბიჯზე, სადაც ეს ამბობდა ის შუა ელემენტს, რომელიც დაწყება + ბოლომდე / 2, ის არის, რომ ტოლია, რაც ჩვენ ვეძებთ? და თუ მას, მაშინ აღმოვაჩინეთ, მაგრამ ვფიქრობ, რომ იღებს გავიდა up დონეზე უკან. და თუ ეს არ არის მართალი, მაშინ ჩვენ შეამოწმოს თუ არა, რომ ახლო ღირებულება array ძალიან დიდი, ამ შემთხვევაში ჩვენ შევხედოთ მარცხენა ნახევარში მასივი მიერ აპირებს დასაწყისიდან შუა ინდექსი. და სხვაგვარად გავაკეთოთ ბოლომდე ნახევარი. [Bowden] Okay. რომ ხმები კარგი. Okay, ასე რამდენიმე რამ, და ფაქტობრივად, ეს არის ძალიან მაღალი დონის რამ რომ თქვენ არასოდეს უნდა იცოდეთ ამ თქმა უნდა, მაგრამ ეს სიმართლეა. რეკურსიული ფუნქციების, ყოველთვის მესმის, რომ ისინი ცუდი გარიგება რადგან თუ რეკურსიული დაირქვით ძალიან ბევრი ჯერ, თქვენ დასტის overflow რადგან, როგორც ვთქვი, ყველა ფუნქცია იღებს საკუთარი დასტის ჩარჩო. ასე რომ ყოველ მოწოდებას რეკურსიული ფუნქცია იღებს საკუთარი დასტის ჩარჩო. ასე რომ, თუ თქვენ გააკეთებთ 1,000 რეკურსიული მოუწოდებს, თქვენ 1,000 დასტის ფარგლებში, და სწრაფად თქვენ გამოიწვიოს მქონე ძალიან ბევრი დასტის ფარგლებში და რამ მხოლოდ შესვენება. ასე ამიტომ რეკურსიული ფუნქციების ზოგადად ცუდი. მაგრამ არსებობს ლამაზი subset of რეკურსიული ფუნქციების მოუწოდა tail-რეკურსიული ფუნქციების და ეს მოხდება, იყოს მაგალითი, სადაც თუ შემდგენელი შეამჩნევს უნდა, ვფიქრობ - ში Clang თუ მსგავ-O2 დროშა მაშინ შეამჩნია ეს კუდი რეკურსიული და მიიღოს რამ კარგი. 

ეს იქნება reuse იგივე დასტის ჩარჩო უსასრულოდ თითოეული რეკურსიული ზარი. და რადგან თქვენ იყენებთ იგივე დასტის ჩარჩო, თქვენ არ გჭირდებათ ფიქრი ოდესმე დააწყობს overflowing, და ამავე დროს, როგორც თქვენ დაწყებამდე განაცხადა, აქ კიდევ თქვენ დაბრუნებას მართალია, მაშინ ის დააბრუნებს ყველა ამ დასტის ფარგლებში და მე -10 ზარი SearchHelp აქვს დაბრუნდეს მე -9, აქვს დაბრუნებას მე -8. ასე რომ არ სჭირდება ხდება ფუნქციებია კუდი რეკურსიული. და მერე რა ხდის ამ ფუნქციის კუდი რეკურსიული არის ცნობა ნებისმიერი მოცემული ზარი searchHelp რეკურსიული მოწოდება, რომ ეს მიღების არის რასაც ის დაბრუნების. ამიტომ პირველ ზარი SearchHelp, ჩვენ არც დაუყოვნებლივ დაბრუნებას ყალბი, დაუყოვნებლივ დაბრუნებას ასეა, ან ჩვენ რეკურსიული ზარი SearchHelp აქ რა ჩვენ დაბრუნების არის რა, რომ ზარის ბრუნდება. და ეს ვერ გავაკეთეთ ეს თითქოს ჩვენ აქ რაღაც int x = SearchHelp, დაბრუნების x * 2, რამოდენიმე შემთხვევითი ცვლილება. 

ახლა ამ რეკურსიული ზარის, ამ int x = SearchHelp რეკურსიული ზარი, აღარ არის კუდი რეკურსიული რადგანაც ეს ფაქტიურად ამჯამად გვაქვს დასაბრუნებელი თავში წინა დასტის ჩარჩო ასე რომ წინა ზარი ფუნქცია შეიძლება მაშინ რაღაც ერთად დაბრუნებული მნიშვნელობა. ასე რომ, ეს არ არის კუდი რეკურსიული, მაგრამ რა გვქონდა ადრე არის ლამაზად კუდი რეკურსიული. Yeah. [სტუდენტი] არ უნდა მეორე ბაზის შემთხვევაში მოწმდება პირველი რადგან შეიძლება იყოს სიტუაცია, სადაც როცა თქვენ გაიაროს ეს არგუმენტი თქვენ არ დაიწყოს = ბოლოს, მაგრამ ისინი ნემსი ღირებულება. შეკითხვა ვერ ჩვენ გადაეყარონ შემთხვევაში ბოლომდე არის ნემსი ღირებულება ან დაიწყოს = ბოლომდე, შესაბამისად, დაიწყოს = ბოლომდე და თქვენ არ რეალურად შემოწმდება, რომ კონკრეტული ღირებულება არ არის, შემდეგ დაიწყება + ბოლომდე / 2 არის მხოლოდ იქნება იგივე ღირებულება. მაგრამ ჩვენ უკვე დაბრუნდა ცრუ და ჩვენ არასოდეს რეალურად შემოწმდება ღირებულება. ამრიგად, სულ მცირე, პირველ ზარი, თუ ზომა არის 0, მაშინ ჩვენ გვინდა დაბრუნების ცრუ. მაგრამ თუ ზომა არის 1, მაშინ დაწყება არ აპირებს თანაბარი ბოლომდე, და ჩვენ მინიმუმ შეამოწმოთ ერთ ელემენტს. მაგრამ, ვფიქრობ, თქვენ უფლება, რომ ჩვენ შეგვიძლია დასრულდება up in შემთხვევაში დაიწყება + ბოლომდე / 2, დაწყება დამთავრდა თუ არა იგივე, რაც დაწყება + ბოლომდე / 2, მაგრამ ჩვენ არასოდეს რეალურად შემოწმდება რომ ელემენტს. 

ასე რომ, თუ ჩვენ პირველად ჩეკი არის შუა ელემენტს ღირებულების ჩვენ ვეძებთ, მაშინ ჩვენ შეგვიძლია დაუყოვნებლივ დაბრუნებას ჭეშმარიტი. Else თუ ისინი თანაბარი, მაშინ არ არსებობს წერტილი გრძელდება რადგან ჩვენ უბრალოდ აპირებს განახლებული შემთხვევაში ჩვენ ერთ ელემენტს მასივი. თუ ეს ერთჯერადი ელემენტს არ არის ერთი ჩვენ ვეძებთ, მაშინ ყველაფერი არასწორია. Yeah. [სტუდენტი] ის არის, რომ მას შემდეგ, რაც ზომა რეალურად აღემატება რაოდენობის ელემენტების მასივი, არსებობს უკვე ოფსეტური - >> ასე იქნება ზომა - [სტუდენტი] Say თუ წყობა იყო ზომა 0, მაშინ SearchHelp რეალურად შევამოწმოთ haystack of 0 პირველ ზარს. Array ზომის 0, ასე რომ 0 არის - >> Yeah. არსებობს კიდევ ერთი რამ, - ეს შეიძლება იყოს კარგი. მოდით ვფიქრობ. ასე რომ, თუ მასივი ჰქონდა 10 ელემენტებს და ახლო ერთი ჩვენ ვაპირებთ შევამოწმოთ არის ინდექსი 5, ამიტომ ჩვენ შემოწმების 5, და ვთქვათ ღირებულება ნაკლებია. ამიტომ ჩვენ სროლა ყველაფერი დაშორებით 5 Onward. ასე რომ დავიწყოთ + ბოლომდე / 2 იქნება ჩვენი ახალი ბოლომდე, ასე yeah, ის ყოველთვის აპირებს დარჩენას მიღმა ბოლოს მასივი. თუ ეს იმ შემთხვევაში, თუ ეს იყო კი ან უცნაური, მაშინ ჩვენ შეამოწმოთ, ვთქვათ, 4, მაგრამ ჩვენ მაინც სროლა მოშორებით - ამიტომ yeah, ბოლოს ყოველთვის იქნება მიღმა ფაქტობრივი ბოლოს მასივი. ამიტომ ელემენტები ჩვენ აქცენტი, ბოლოს ყოველთვის იქნება ერთი ამის შემდეგ. და თუ დაწყება არ ოდესმე თანაბარი ბოლოს, ჩვენ ვართ მასივი ზომა 0. 

სხვა რამ მე აზროვნება ჩვენ განახლებაზე დაწყება უნდა დაიწყოს + ბოლომდე / 2, ასე რომ, ეს საქმე რომ მე მქონე უბედურება ერთად, სადაც დაიწყება + ბოლომდე / 2 არის ელემენტს ჩვენ შემოწმების. ვთქვათ ჩვენ გვქონდა ამ 10-ელემენტს მასივი. როგორიც არ უნდა იყოს. ასე რომ დავიწყოთ + ბოლომდე / 2 იქნება რაღაც მსგავსი ერთი, და თუ ეს ასე არ არის ღირებულება, ვთქვათ გვინდა განახლება. ღირებულება მეტია, ამიტომ ჩვენ გვინდა შევხედოთ ამ ნახევარში მასივი. მაშ როგორ ჩვენ განახლებაზე დაწყება, ჩვენ განახლებაზე დასაწყისიდან ახლა ამ ელემენტს. მაგრამ ეს შეიძლება კვლავ მუშაობენ, ან სულ მცირე, შეგიძლიათ გააკეთოთ დაწყება + ბოლომდე / 2 + 1. [სტუდენტი] თქვენ არ უნდა იყოს დაიწყოს + ბოლომდე [inaudible] >> Yeah. ჩვენ უკვე გადამოწმებული ელემენტს და იციან, არ ერთი ჩვენ ვეძებთ. ამიტომ, ჩვენ არ გვჭირდება განახლება დაწყება უნდა იყოს ამ ელემენტს. ჩვენ შეგვიძლია მხოლოდ გამოტოვოთ იგი და განაახლოთ დაიწყებს იყოს ამ ელემენტს. და იქ ოდესმე შემთხვევაში, ვთქვათ, რომ ეს იყო ბოლომდე, ასეა, მაშინ დაიწყება იქნებოდა ამ, დაიწყოს + ბოლომდე / 2 იქნება ეს, დაიწყოს + ბოლომდე - ჰო, მე ვფიქრობ, რომ შეიძლება დასრულდეს up in უსასრულო უკან. ვთქვათ უბრალოდ მასივი ზომა 2 ან მასივი ზომა 1. ვფიქრობ, ეს იმუშავებს. ასე გაკეთებული, დაწყება არის ის, რომ ელემენტს და ბოლომდე არის 1 მის ფარგლებს გარეთ. ასე ელემენტს, რომ ჩვენ ვაპირებთ შევამოწმოთ ეს ერთი, და მაშინ, როდესაც ჩვენ განაახლოთ დაწყება, ჩვენ განახლებაზე დაწყება უნდა იყოს 0 + 1/2, რომელიც აპირებს დასრულდება us უკან დაწყება მყოფი ამ ელემენტს. 

ამიტომ ჩვენ შემოწმების იმავე ელემენტს უსასრულოდ. ასე რომ, ეს საქმე, სადაც ყველა რეკურსიული ზარის უნდა რეალურად განაახლოთ რაღაც. ამიტომ, ჩვენ უნდა გავაკეთოთ დაწყება + ბოლომდე / 2 + 1, ანდა არსებობს შემთხვევაში სადაც ჩვენ რეალურად არ განახლებაზე დაწყება. ყველამ დაინახოს, რომ? Okay. ვინმეს აქვს კითხვები ამ გადაწყვეტა ან რაიმე სხვა კომენტარები? Okay. ვინმეს არ iterative გადაწყვეტა, რომ ჩვენ შეგვიძლია ყველა შევხედოთ? ხომ ჩვენ ყველა გავაკეთებთ რეკურსიული? ან ასევე ვფიქრობ, თუ თქვენ გაიხსნა hers, მაშინ შესაძლოა თქვენი ჩანაცვლების წინა. იგი ავტომატურად შენახვა? მე არ ვარ დადებითი. ვინმეს არ iterative? ჩვენ შეგვიძლია გავლა ერთად, თუ არ. იდეა იქნება იგივე. Iterative გადაწყვეტა. ჩვენ ვაპირებთ გვინდა ძირითადად იგივე იდეა სად გვინდა ტრეკზე ახალი ბოლომდე array და ახალი დაწყების მასივი და გავაკეთოთ, რომ მეტი და მეტი. და თუ რა ჩვენ შენახვა ტრეკზე როგორც დაწყება და ბოლომდე ოდესმე იკვეთება, მაშინ ჩვენ ვერ და ჩვენ შეგვიძლია დაბრუნების ცრუ. მაშ როგორ შემიძლია ამის გაკეთება? ვინმეს აქვს წინადადებები ან კოდი ჩემთვის დახევის up? [სტუდენტი] Do ხოლო loop. >> Yeah. აპირებთ გსურთ loop. 

გქონდათ კოდი შემეძლო დახევის up ან რა იყო აპირებთ ვარაუდობენ? [სტუდენტი] ვფიქრობ ასე. >> ყველა უფლება. ეს ხდის რამ ადვილია. რა იყო თქვენი სახელი? [სტუდენტი] Lucas. ცვლილებათა 1. Okay. დაბალი არის, რაც ჩვენ მოუწოდა დაიწყოს. Up დიდი ხნის არ არის, რაც ჩვენ მოუწოდა ბოლომდე ადრე. რეალურად, ბოლოს არის ფარგლებში მასივი. ეს ელემენტს უნდა გავითვალისწინოთ. იმდენად დაბალია არის 0, up არის ზომა მასივი - 1, და ახლა ჩვენ looping და ჩვენ შემოწმების - ვფიქრობ შეგიძლიათ გავლა იგი. რა იყო თქვენი აზროვნების მეშვეობით? Walk us საშუალებით თქვენი კოდი. [სტუდენტი] რა თქმა უნდა. შეხედეთ haystack ღირებულების საშუალო და შეადაროთ იგი ნემსი. ასე რომ, თუ ის აღემატება თქვენი ნემსი, შემდეგ გსურთ - Oh, რეალურად, რომ უნდა იყოს უკან. თქვენ ვაპირებთ გვინდა გადაყარეთ მარჯვენა ნახევარში, და ისე ჰო, უნდა იყოს გზა. [Bowden] ასე რომ, ეს უნდა იყოს ნაკლები? ის არის, რომ ის, რაც თქვენ თქვით? >> [სტუდენტი] Yeah. [Bowden] Okay. ნაკლებია. ასე რომ, თუ რა ჩვენ შევხედავთ მცირეა, რაც ჩვენ გვინდა, მაშინ ჰო, ჩვენ გვინდა გადაყარეთ მარცხენა ნახევარში, რაც იმას ნიშნავს, რომ ჩვენ განახლებაზე ყველაფერი ჩვენ გათვალისწინებით გადაადგილების დაბალი მარჯვნივ მასივი. ეს გამოიყურება კარგი. მე ვფიქრობ, რომ აქვს იგივე საკითხი, რომელიც ჩვენ განაცხადა ადრე, აქ თუ არის დაბალი 0 და 1, მაშინ დაბალი + up / 2 აპირებს შექმნას იქნება იგივე ერთხელ. 

და მაშინაც კი, თუ ეს ასე არ არის საქმე, ეს კიდევ უფრო ეფექტური სულ ცოტა უბრალოდ გადააგდებს ელემენტს ჩვენ უბრალოდ შევხედე, რომელიც ჩვენ ვიცით, არასწორია. იმდენად დაბალია + up / 2 + 1 - >> [სტუდენტი], რომ უნდა იყოს სხვა გზა. [Bowden] ან ეს უნდა იყოს - 1 და მეორე უნდა იყოს + 1. [სტუდენტი] და იქ უნდა იყოს ორმაგი ტოლობის ნიშანი. >> [Bowden] Yeah. [სტუდენტი] Yeah. Okay. და ბოლოს, ახლა რომ ჩვენ გვაქვს ეს + 1 - 1 რამ, არის იგი - ეს შესაძლოა არ იყოს - ეს არის ის ოდესმე შესაძლებელი დაბალი დასრულდება up ერთად ღირებულება აღემატება up? ვფიქრობ ერთადერთი გზა, რომელიც შეიძლება მოხდეს - შეიძლება თუ არა? >> [სტუდენტი] არ ვიცი. მაგრამ თუ იგი იღებს truncated და შემდეგ იღებს მინუს რომ 1 და შემდეგ - >> Yeah. [სტუდენტი] უმჯობესი შესაძლოა მიიღოთ არევა. მე ვფიქრობ, ეს უნდა იყოს კარგი მხოლოდ იმიტომ მას მოხვდნენ ქვედა ისინი უნდა იყოს თანასწორი, ვფიქრობ. მაგრამ თუ ისინი თანაბარი, მაშინ ჩვენ არ გავაკეთეთ, ხოლო loop დავიწყოთ და ჩვენ უბრალოდ იქნებოდა დაბრუნებული მნიშვნელობა. ამიტომ, მე ვფიქრობ, რომ ჩვენ კარგად არის. გაითვალისწინეთ, რომ მიუხედავად იმისა, რომ ეს პრობლემა აღარ არის რეკურსიული, მსგავსი იდეები ვრცელდება, სადაც ჩვენ ვხედავთ, თუ როგორ ეს ასე ადვილად lends თავად to რეკურსიული გამოსავალი ის ფაქტი, რომ ჩვენ უბრალოდ განახლებას ინდექსების უსასრულოდ, ჩვენ მიღების პრობლემა პატარა და პატარა, ჩვენ აქცენტი subset of მასივი. [სტუდენტი] თუ დაბალი არის 0 და 1, ისინი ორივე იყოს 0 + 1/2, რომელიც წავიდოდა 0, და მაშინ ერთი იქნება + 1, ერთი იქნება - 1. [სტუდენტი] სად ვიმყოფებით შემოწმების თანასწორობის? Like თუ ახლო ერთი ფაქტიურად ნემსი? ჩვენ არ ამჟამად აკეთებს, რომ? Oh! თუ it's - დიახ. ჩვენ არ შეგვიძლია უბრალოდ ტესტი ქვემოთ აქ იმიტომ ვთქვათ პირველი ახლო - [სტუდენტი] სინამდვილეში მინდა არ გადაყარეთ ბლოკნოტებს. ასე რომ, თუ თქვენ გადაყარეთ შეკრული, თქვენ უნდა შეამოწმეთ იგი პირველი ან რასაც. Ah. Yeah. >> [სტუდენტი] Yeah. ახლა ჩვენ დააგდეს დაშორებით ერთი ჩვენ გაკეთებული შევხედე, რაც იმას ნიშნავს, რომ ჩვენ ახლა გვჭირდება ასევე აქვს თუ (haystack [(დაბალი + up) / 2] == ნემსი), მაშინ ჩვენ შეგვიძლია იქნება TRUE. და თუ არა მე ზუსტად სხვაგან, ან უბრალოდ თუ, ეს ნიშნავს სიტყვასიტყვით იგივე რადგან ეს იქნებოდა დაბრუნებული ჭეშმარიტი. ამიტომ მე დააყენა სხვაგან თუ, მაგრამ არა აქვს მნიშვნელობა. 

ასე რომ სხვაგან თუ ეს, სხვას ეს, და ეს არის საერთო რამ გავაკეთო აქ თუნდაც ის შემთხვევაა, როდესაც ყველაფერი კარგი აქ, მოსწონს დაბალი არ შეიძლება მეტი up, ეს არ ღირს მსჯელობა იმის შესახებ, რომ მართალია. ასე, რომ თქვენ შეიძლება ასევე აცხადებენ, ხოლო დაბალი ნაკლებია ან ტოლი ან მაშინ, როცა დაბალი ნაკლებია, ვიდრე ასე რომ, თუ ისინი ოდესმე თანაბარი ან დაბალი ხდება გაიაროს up, მაშინ ჩვენ შეგვიძლია დაარღვიოს ამ loop. კითხვები, შეშფოთება, კომენტარი? Okay. ეს გამოიყურება კარგი. ახლა ჩვენ გვინდა გავაკეთოთ ჯიშია. თუ ჩვენ გადასვლა ჩემს მეორე ვერსიასთან, ჩვენ ვხედავთ ამ საერთო ნომრები, მაგრამ ახლა ისინი აღარ დახარისხებული მიზნით. და გვინდა განხორციელება დალაგების გამოყენებით ნებისმიერი ალგორითმი O of n შესვლა n. ასე რომ რაც ალგორითმი ფიქრობთ უნდა განახორციელოს აქ? >> [სტუდენტი] Merge ჯიშია. [Bowden] Yeah. შერწყმა დალაგების არის O (N შესვლა N), ისე, რომ ის, რასაც ჩვენ ვაპირებთ. და პრობლემა იქნება საკმაოდ მსგავსია, სადაც მას ადვილად lends თავს რეკურსიული გადაწყვეტა. ჩვენ შეგვიძლია ასევე ამუშავება iterative გამოსავალი თუ გვინდა, მაგრამ უკან იქნება ადვილი აქ და ჩვენ უნდა გავაკეთოთ უკან. ვფიქრობ ჩვენ გავლა შერწყმა დალაგების პირველი, თუმცა არსებობს lovely ვიდეო შერწყმა დალაგების უკვე. [სიცილის] ასე რომ შერწყმა დალაგების არსებობს - მე გაყვანაა იმდენად, რამდენადაც ეს ქაღალდი. ოჰ, მხოლოდ ერთი მარცხენა. ასე რომ შერწყმა. Oh, 1, 3, 5. Okay. Merge იღებს ორი დამოუკიდებელი მასივები. ინდივიდუალურად იმ ორი კოლექტორები ორივე დახარისხებული. ასე რომ, ეს მასივი, 1, 3, 5, დახარისხებული. ეს მასივი, 0, 2, 4, დახარისხებული. ახლა რა შერწყმა უნდა გავაკეთოთ არის დააკავშიროთ მათ ერთ მასივი, რომელიც თავად დახარისხებული. ასე რომ ჩვენ გვინდა მასივი ზომა 6 რომ აპირებს აქვს ამ ელემენტების შიგნით ეს წელს დახარისხებული მიზნით. 

ასე რომ, ჩვენ შეიძლება ისარგებლოს იმ ფაქტს, რომ ამ ორი კოლექტორები რომლებიც დალაგებულია ამის გაკეთება წელს ხაზოვანი დროს, ხაზოვანი ახლა მნიშვნელობა, თუ ამ მასივი ზომა x და ეს ზომა Y, მაშინ სულ ალგორითმი უნდა იყოს O (x + y). Okay. ასე წინადადებები. [სტუდენტი] ვერ დავიწყებთ მარცხნიდან? ასე რომ თქვენ დააყენა 0 ქვემოთ და შემდეგ 1 და შემდეგ აქ თქვენ დროს 2. ასე რომ სახის მოსწონს გაქვთ tab რომ გადასვლის უფლება. >> [Bowden] Yeah. ორივე ეს კოლექტორები თუ ჩვენ მხოლოდ ფოკუსირება leftmost ელემენტს. იმის გამო, რომ ორივე კოლექტორები რომლებიც დალაგებულია, ჩვენ ვიცით, რომ ეს 2 ელემენტები არის პატარა ელემენტები ორივე მასივი. ასე რომ, რაც იმას ნიშნავს, რომ 1 იმ 2 ელემენტები უნდა იყოს პატარა ელემენტს ჩვენს შერწყმული მასივი. ეს უბრალოდ ისე ხდება, რომ პატარა არის ერთი მარჯვენა ამ დროს. ამიტომ ჩვენ ვიღებთ 0, ჩადეთ ის მარცხენა რადგან 0 ნაკლებია, ვიდრე 1, ასე მიიღოს 0, ჩადეთ იგი ჩვენი პირველი პოზიცია, და შემდეგ ჩვენ განაახლოთ აქამდე ფოკუსირებული პირველ ელემენტს. და ახლა ჩვენ ვიმეორებთ. ახლა შევადარებთ 2 და 1. 1 არის პატარა, ამიტომ ჩვენ ჩადეთ 1. ჩვენ განაახლოთ მომცეთ აღვნიშნო, რომ ამ ბიჭს. ახლა ჩვენ გავაკეთებთ ერთხელ, ასე რომ 2. ეს განაახლებს, შევადარებთ ამ 2, 3. ეს განახლება, მაშინ 4 და 5. ასე რომ არის შერწყმა. 

იგი უნდა იყოს საკმაოდ აშკარაა, რომ ეს არის ხაზოვანი ახლა რადგან ჩვენ უბრალოდ მასშტაბით თითოეული ელემენტის ერთხელ. და ეს არის ყველაზე დიდი ნაბიჯი განხორციელების შერწყმა sort აკეთებს ამ. და ეს არ არის რთული. რამდენიმე რამ ფიქრი არის ვთქვათ ჩვენ შერწყმის 1, 2, 3, 4, 5, 6. ამ შემთხვევაში ჩვენ დასრულდება მდე წელს სცენარი, სადაც ეს ერთი იქნება პატარა, მაშინ ჩვენ განაახლოთ მაჩვენებელი, ამ ერთი იქნება პატარა, განაახლოთ, ამ ერთი პატარა, და ახლა თქვენ უნდა აღიაროს როდესაც თქვენ ფაქტიურად ამოიწურა ელემენტების შედარებით. მას შემდეგ, რაც ჩვენ უკვე გამოიყენება მთელი მასივი, ყველაფერი ამ array არის მხოლოდ ჩასმული შევიდა აქ. ასე რომ, თუ ჩვენ ოდესმე გადაეყარონ წერტილში, სადაც ჩვენი ერთი მასივები მთლიანად გაერთიანდა უკვე, მაშინ ჩვენ უბრალოდ მიიღოს ყველა ელემენტების სხვა array და ჩადეთ მათთვის ბოლომდე მასივი. ასე რომ ჩვენ შეგვიძლია მხოლოდ ჩადეთ 4, 5, 6. Okay. სწორედ ერთია ფრთხილად. განხორციელება, რომ უნდა იყოს ნაბიჯი 1. შერწყმა დასალაგებლად შემდეგ ეფუძნება, რომ ეს 2 ნაბიჯები, 2 სულელური ნაბიჯები. მოდით უბრალოდ მისცეს ამ მასივი. ასე რომ შერწყმა დახარისხების, ნაბიჯი 1 არის რეკურსიული შესვენება მასივი შევიდა halves. ასე გაყოფილი ამ მასივი შევიდა halves. ჩვენ გვყავს 4, 15, 16, 50 და 8, 23, 42, 108. და ახლა ჩვენ გავაკეთებთ ერთხელ და ჩვენ გაყოფილი ამ შევიდა halves. მე მხოლოდ ამის შესახებ ამ მხარეს. ასე 4, 15 და 16, 50. ჩვენ ყველაფერს გააკეთებს იგივე აქ. და ახლა ჩვენ გაყოფილი იგი halves ერთხელ. ჩვენ გვყავს 4, 15, 16, 50. ასე რომ ჩვენი ბაზის შემთხვევაში. ერთხელ კოლექტორები არის ზომა 1, მაშინ ჩვენ შეწყვიტოს ერთად გაყოფის შევიდა halves. 

ახლა რას ვაკეთებთ ამ? ჩვენ დასრულდება მდე ამ ასევე ჩაშლის შევიდა 8, 23, 42, და 108. ახლა რომ ჩვენ ამ ეტაპზე, ახლა დაიხევს ორი შერწყმა დალაგება მხოლოდ შერწყმის წყვილი რათა სიები. ასე რომ ჩვენ გვინდა შერწყმა ამ. ჩვენ უბრალოდ ვუწოდებთ შერწყმა. ჩვენ ვიცით, შერწყმა დაბრუნდება ამ წელს დახარისხებული მიზნით. 4, 15. ახლა ჩვენ გვინდა შერწყმა ამ, და რომ დაბრუნდება სია იმ დახარისხებული მიზნით, 16, 50. ჩვენ შერწყმა იმ - ვერ წერენ - 8, 23 და 42, 108. ამიტომ ჩვენ გვაქვს გაერთიანებული წყვილი ერთხელ. ახლა ჩვენ მხოლოდ შერწყმა ერთხელ. გაითვალისწინეთ, რომ თითოეული ეს სიები დალაგებულია თავისთავად, და მაშინ ჩვენ შეგვიძლია მხოლოდ შერწყმა ამ სიებს კიდევ სიაში ზომა 4 რომელიც დახარისხებული და შერწყმის ამ ორი სიები მისაღებად სიაში ზომა 4 რომ დალაგებულია. და ბოლოს, ჩვენ შეგვიძლია შერწყმა ამ ორი სიები ზომა 4 მისაღებად ერთ სიაში ზომა 8 რომ დალაგებულია. ასე, რომ ეს არის საერთო N შესვლა N, ჩვენ უკვე ვნახეთ, რომ შერწყმა არის წრფივი, ასე რომ, როდესაც ჩვენ საქმე შერწყმის ამ, ასე მოსწონს საერთო ღირებულება შერწყმა ამ ორი სიები მხოლოდ 2 რადგან - ან ისე, ეს O of n, მაგრამ n აქ მხოლოდ ამ 2 ელემენტებს, ამიტომ 2. და ამ 2 იქნება 2 და ამ 2 იქნება 2 და ამ 2 იქნება 2, ასე მასშტაბით ყველა შერწყმების, რომ ჩვენ უნდა გავაკეთოთ, ჩვენ დასრულდება მდე აკეთებს n. Like 2 + 2 + 2 + 2 არის 8, რომელიც N, ასე ღირებულება შერწყმის ამ კომპლექტი არის n. და შემდეგ იგივე აქ. ჩვენ შერწყმა ამ 2, მაშინ ეს 2 და ინდივიდუალურად ამ შერწყმა მიიღებს ოთხი ოპერაციები, ამ შერწყმა მიიღებს ოთხი ოპერაციების, მაგრამ კიდევ ერთხელ, შორის ყველა ჩამოთვლილს, ჩვენ დასრულდება მდე შერწყმის N სულ რამ, და ა.შ. ეს ნაბიჯი იღებს n. და ა.შ. თითოეულ დონეზე იღებს n ელემენტებს მიმდინარეობს გაერთიანდა. 

და რამდენი დონეზე არსებობს? თითოეულ დონეზე, ჩვენი მასივი იზრდება ზომა 2. აქ ჩვენი კოლექტორები არის ზომა 1, აქ ისინი საქართველოში ზომა 2, აქ ისინი of ზომა 4, და ბოლოს, ისინი საქართველოს ზომა 8. , რადგან ეს გააორმაგოს, იქ ვაპირებთ იყოს სულ შესვლა n ამ დონეზე. ამრიგად შესვლა N დონეზე, თითოეული დონის აღების N სულ ოპერაციები, მივიღებთ N შესვლა N ალგორითმი. კითხვები? არ ხალხი უკვე მიაღწია პროგრესს, თუ როგორ უნდა განახორციელოს ეს? არის ვინმე უკვე იმ სახელმწიფოში, სადაც მე შემიძლია მხოლოდ გაიყვანოს საკუთარი კოდი? მე შემიძლია მოგცეთ წუთი. ეს ერთი იქნება აღარ. უაღრესად გირჩევთ recur - თქვენ არ უნდა გავაკეთოთ უკან ამისთვის შერწყმა რადგან გავაკეთოთ უკან ამისთვის შერწყმა, თქვენ აპირებს უნდა გაიარონ bunch სხვადასხვა ზომის. თქვენ შეგიძლიათ, მაგრამ შემაშფოთებელი. მაგრამ უკან დაბრუნების მიზნით დალაგება თავისთავად საკმაოდ მარტივია. თქვენ უბრალოდ სიტყვასიტყვით მოვუწოდებთ დალაგების მარცხენა ნახევარში, დალაგება მარჯვენა ნახევარში. Okay. ვინმეს აქვს რამე შემიძლია დახევის დღემდე? ანდა მე მივცემ წუთი. Okay. ვინმეს აქვს რაიმე შეგვიძლია ვიმუშაოთ? ანდა ჩვენ მხოლოდ მუშაობა ამ და შემდეგ გაფართოებას იქიდან. 

ვინმეს აქვს მეტი, ვიდრე ეს რომ შემიძლია დახევის up? [სტუდენტი] Yeah. შეგიძლიათ დახევის up აფეთქდა. >> ყველა უფლება. დიახ! [სტუდენტი] იყო ბევრი პირობები. >> Oh, დახვრიტეს. შეგიძლიათ - [სტუდენტი] მე უნდა შეინახოთ. >> Yeah. ამიტომ ჩვენ გავაკეთებთ შერწყმა ცალკე. ოჰ, მაგრამ ეს არ არის, რომ ცუდი. Okay. ასე დალაგება თავისთავად მხოლოდ მოუწოდებდა mergeSortHelp. ავუხსნათ თუ რას აკეთებს mergeSortHelp. [სტუდენტი] MergeSortHelp საკმაოდ ღირს ორი ძირითადი ნაბიჯები, რომელიც დასალაგებლად ყოველ ნახევარში array და შემდეგ შერწყმა ორივე მათგანი. [Bowden] Okay, ასე მომეცი მეორე. ვფიქრობ, ეს - >> [სტუდენტი] მე უნდა - Yeah. მე გავიგე რამე. In შერწყმა, ვხვდები, რომ მე უნდა შევქმნათ ახალი მასივი იმიტომ, რომ მე ვერ გავაკეთეთ ადგილზე. >> დიახ. თქვენ არ შეგიძლიათ. სწორი. [სტუდენტი] ასე, რომ შევქმნათ ახალი მასივი. დამავიწყდა დასასრულს შერწყმა ხელახლა შეიცვალოს. Okay. ჩვენ გვჭირდება ახალი მასივი. In შერწყმა დახარისხების, ეს არის თითქმის ყოველთვის მართალია. ნაწილი ღირებულება უკეთესი ალგორითმი დროის ბრძენი თითქმის ყოველთვის სჭირდება გამოიყენოს უფრო მეტი მეხსიერება. ასე რომ აქ, არ აქვს მნიშვნელობა, თუ როგორ გავაკეთოთ შერწყმა დახარისხების, თქვენ აუცილებლად უნდა გამოვიყენოთ ზოგიერთი დამატებითი მეხსიერება. მან შექმნა ახალი მასივი. და მაშინ ამბობენ დასასრულს ჩვენ უბრალოდ უნდა კოპირება ახალი მასივი შევიდა ორიგინალური მასივი. [სტუდენტი] ვფიქრობ ასე, yeah. მე არ ვიცი, თუ, რომელიც მუშაობს თვალსაზრისით დათვლის მიერ მინიშნება ან რასაც - ჰო, ის იმუშავებს. >> [სტუდენტი] Okay. გსმენიათ ვცდილობთ გაშვებული ამ? >> [სტუდენტი] არა, არ გაუკეთებია. >> Okay. სცადეთ გაშვებული, და მაშინ მე ამაზე მეორე. [სტუდენტი] მე უნდა ჰქონდეს ყველა ფუნქციის პროტოტიპები და ყველაფერი, თუმცა, არა? ფუნქციის პროტოტიპები. ოჰ, შენ ნიშნავს, როგორიცაა - დიახ. დალაგების მოუწოდებს mergeSortHelp. 

ამიტომ იმისათვის, დალაგება მოვუწოდო mergeSortHelp, mergeSortHelp უნდა ან არ არის განსაზღვრული ადრე დალაგების ან ჩვენ უბრალოდ უნდა პროტოტიპი. გადააკოპირეთ და ჩასვით რომ. და ანალოგიურად, mergeSortHelp მოუწოდებს შერწყმა, მაგრამ შერწყმა არ არის დადგენილი, ამიტომ ჩვენ შეგვიძლია უბრალოდ ნება mergeSortHelp ვიცი რომ სწორედ შერწყმა აპირებს ჰგავს, და ეს რომ. ამიტომ mergeSortHelp. ჩვენ გვყავს საკითხი აქ, სადაც ჩვენ არ გვაქვს ბაზა შემთხვევაში. MergeSortHelp არის რეკურსიული, ამიტომ ნებისმიერი რეკურსიული ფუნქცია სჭირდება გარკვეული ბაზა საქმე იცით, როდესაც შეჩერება რეკურსიული მოუწოდებდა თავად. რა არის ჩვენი ბაზის შემთხვევაში იქნება აქ? Yeah. [სტუდენტი] თუ ზომა არის 1? >> [Bowden] დიახ. ასე რომ როგორც ჩვენ ვნახეთ უფლება არსებობს, ჩვენ შეწყვიტა გაყოფა კოლექტორები ერთხელ ჩვენ ჩასხდნენ კოლექტორები of ზომა 1, რომელიც აუცილებლად არიან დახარისხებული თავს. ასე რომ, თუ ზომა შეადგენს 1, ვიცით მასივი უკვე დახარისხებული, ამიტომ ჩვენ შეგვიძლია უბრალოდ დააბრუნოს. 

გაითვალისწინეთ, რომ ბათილად, ამიტომ ჩვენ არ დაბრუნდებიან არაფერი განსაკუთრებული, უბრალოდ, დაბრუნდნენ. Okay. ასე რომ ჩვენი ბაზის შემთხვევაში. ვფიქრობ ჩვენი ბაზის შემთხვევაში შეიძლება, თუ ჩვენ არ უნდა იყოს შერწყმის მასივი ზომა 0, ჩვენ ალბათ სურთ შეწყვიტონ რაღაც მომენტში, ამიტომ ჩვენ შეგვიძლია უბრალოდ, ვამბობთ ზომა არანაკლებ 2 ან ნაკლები ან ტოლია 1 ასე, რომ ეს იმუშავებს ნებისმიერი array არის. Okay. ასე რომ ჩვენი ბაზის შემთხვევაში. ახლა გინდა ფეხით ჩვენს მეშვეობით შერწყმა? რა ყველა ამ შემთხვევაში ნიშნავს? აქ, ჩვენ უბრალოდ აკეთებს იგივე იდეას, - [სტუდენტი] მე უნდა იყოს ავლით ზომა ყველა mergeSortHelp მოუწოდებს. მე დასძინა ზომა როგორც დამატებითი პირველადი და ეს არ არსებობს, ისევე, როგორც ზომა / 2. [Bowden] Oh, ზომა / 2, ზომა / 2. >> [სტუდენტი] ჰო, და ასევე ზემოთ ფუნქციის ისევე. [Bowden] აქ? >> [სტუდენტი] უბრალოდ ზომა. >> [Bowden] Oh. ზომა, ზომა? >> [სტუდენტი] Yeah. [Bowden] Okay. ნება მომეცით ვფიქრობ, მეორე. ჩვენ გადაეყარონ საკითხი? ჩვენ ყოველთვის მკურნალობის მარცხენა როგორც 0. >> [სტუდენტი] ჯგუფი სწორედ არასწორი ძალიან. უკაცრავად. ეს უნდა იყოს დაწყება. Yeah. [Bowden] Okay. მომწონს, რომ უკეთესი. და დასასრული. Okay. ახლა გინდა ფეხით ჩვენს მეშვეობით შერწყმა? >> [სტუდენტი] Okay. მე უბრალოდ გავლით ამ ახალი მასივი, რომ მე შევქმენით. მისი ზომა არის ზომა ნაწილი მასივი, რომ ჩვენ გვინდა იყოს დახარისხებული და ცდილობს იპოვოს ელემენტს, რომ მე უნდა ჩაიდოს ახალი მასივი ნაბიჯი. ასე გავაკეთოთ, რომ, პირველი მე შემოწმების თუ მარცხენა ნახევარში მასივი აგრძელებს რაიმე მეტი ელემენტები, და თუ ეს არ მოხდა, მაშინ ქვევით რომ სხვაგან მდგომარეობა, რომელიც მხოლოდ ამბობს Okay, ეს უნდა იყოს სწორი მასივი, და ჩვენ დააყენა, რომ მიმდინარე ინდექსი newArray. 

და შემდეგ სხვაგვარად, მე შემოწმების თუ მარჯვენა მხარეს მასივი ასევე დასრულდა, ამ შემთხვევაში მე უბრალოდ დასვა მარცხენა. შესაძლოა, სწორედ ამით რეალურად არ იყოს საჭირო. მე არ ვარ დარწმუნებული. მაგრამ მაინც, ხოლო დანარჩენი ორი გამშვები რომელი ორი პატარა ქალაქ მარცხნივ ან მარჯვნივ. და ასევე ყოველ შემთხვევაში, მე დამატება რომელი placeholder I იყოს. [Bowden] Okay. რომელიც გამოიყურება კარგი. ვინმეს აქვს კომენტარი ან შეშფოთება ან კითხვები? ასე რომ ოთხი შემთხვევებში, რომ გვაქვს, რათა რამ შევიდა მხოლოდ კონკრეტდება - ან გამოიყურება ხუთი - მაგრამ იმის გათვალისწინებით, თუ რამდენად მარცხენა მასივი უკვე ამოიწურა რამ უნდა შერწყმა, თუ არა უფლება მასივი უკვე ამოიწურა რამ უნდა შერწყმა - მე მიუთითებს არაფერი. ასე თუ არა მარცხენა მასივი უკვე ამოიწურა რამ ან უფლება მასივი უკვე ამოიწურა რამ. ეს ის ორი შემთხვევა. ჩვენ ასევე გვჭირდება ტრივიალური შემთხვევაში თუ არა მარცხენა რამ არის ნაკლები ვიდრე სწორი. მაშინ ჩვენ გვინდა აირჩიოს მარცხენა რამ. იმ შემთხვევებში. ასე რომ, ეს იყო სწორი, ასე რომ, რომ. Array დაუტოვებიათ. ეს 1, 2, 3. Okay. ამიტომ yeah, ეს ის ოთხი რამ შეიძლება გსურთ. და ჩვენ არ წავიდეთ მეტი iterative გადაწყვეტა. არ ვურჩევთ - შერწყმა დალაგების არის მაგალითი ფუნქცია, რომელიც ორივე არ კუდი რეკურსიული, ეს არ არის ადვილი, რათა ის კუდი რეკურსიული, არამედ ეს არ არის ძალიან ადვილია, რათა ის iterative. ეს ძალიან მარტივია. ეს განხორციელებას შერწყმა დახარისხების, შერწყმა, არ აქვს მნიშვნელობა, თუ რას აკეთებთ, თქვენ აპირებს ააშენოს შერწყმა. 

ასე რომ შერწყმა დალაგების აგებული ზევით შერწყმა რეკურსიული მხოლოდ ამ სამი ხაზები. Iteratively, ეს უფრო შემაშფოთებელი და უფრო რთული ვიფიქროთ. მაგრამ შეამჩნია, რომ ეს არ კუდი რეკურსიული წლიდან mergeSortHelp - როდესაც ის მოუწოდებს თავად - იგი ჯერ კიდევ გავაკეთოთ რამ ამის შემდეგ რეკურსიული ზარის ბრუნდება. ასე რომ, ეს დასტის ჩარჩოში უნდა განაგრძოს არსებობას შემდეგაც კი მოუწოდებდა ამ. და მაშინ, როდესაც თქვენ დაარქვით, დასტის ჩარჩოში უნდა განაგრძოს არსებობს რადგან შემდეგაც კი ეს გამოძახილი, ჩვენ მაინც უნდა შერწყმა. და ეს nontrivial რათა ამ კუდი რეკურსიული. კითხვები? ყველა უფლება. ასე რომ დაუბრუნდეს დასალაგებლად - Oh, არსებობს ორი რამ მინდა ნახოთ. Okay. უკან დასალაგებლად, ჩვენ გავაკეთებთ ამ სწრაფად. ან ძებნის. დალაგება? დალაგება. Yeah. ბრუნდება დასაწყისი ჯიშია. ჩვენ გვინდა რომ შევქმნათ ალგორითმი რომ სახის მასივი გამოყენებით ნებისმიერი ალგორითმი წელს O of n. მაშ როგორ არის ეს შესაძლებელი? ვინმეს აქვს რაიმე სახის - მე მიანიშნა ადრე at - თუ ჩვენ შესახებ გასაუმჯობესებლად საწყისი N შესვლა n to O of n, ჩვენ გაუმჯობესდა ჩვენი ალგორითმი დროის ბრძენი, რაც იმას ნიშნავს, რას ვაპირებთ გვჭირდება შეადგინოს ამისთვის? [სტუდენტი] ფართი. >> Yeah. ჩვენ ვაპირებთ იყოს გამოყენებით მეტი სივრცე. და არც კი მხოლოდ მეტი სივრცე, ეს exponentially მეტი სივრცე. ამიტომ ვფიქრობ ამ ტიპის ალგორითმი ფსევდო რაღაც, ფსევდო polynom - ფსევდო - მე არ მახსოვს. ფსევდო რაღაც. მაგრამ ეს იმიტომ, რომ ჩვენ უნდა გამოვიყენოთ იმდენად სივრცეში რომ ეს მიღწევადია, მაგრამ არა რეალისტური. 

და როგორ უნდა მივაღწიოთ ამას? ჩვენ შეგვიძლია მივაღწიოთ ამ შემთხვევაში ჩვენ ვიძლევით გარანტიას, რომ რომელიმე კონკრეტულ ელემენტს მასივი ქვემოთ არის გარკვეული ზომით. მოდით უბრალოდ, ვამბობთ, რომ ზომა არის 200, ნებისმიერი ელემენტი მასივი ქვემოთ ზომა 200. და ეს არის ძალიან რეალისტური. თქვენ შეგიძლიათ ძალიან მარტივად აქვს მასივი, რომ თქვენ იცით, ყველაფერი ეს იქნება ნაკლები გარკვეული რაოდენობის. Like თუ გაქვთ აბსოლუტურად მასიური ვექტორი ან რამე მაგრამ თქვენ იცით, ყველაფერი იქნება შორის 0 და 5, მაშინ იქნება მნიშვნელოვნად უფრო სწრაფად ამის გაკეთება. და ბლოკნოტებს ნებისმიერ ელემენტებს არის 5, ასე რომ ეს შეკრული, რომ არის, თუ რამდენი მეხსიერება თქვენ უნდა გამოყენებით. ასე რომ ბლოკნოტებს არის 200. თეორიულად ყოველთვის არის შეკრული, რადგან მთელი რიცხვი უნდა იყოს მხოლოდ მდე 4 მილიარდი, მაგრამ ეს არარეალურია, რადგან მაშინ ჩვენ მინდა იყოს გამოყენებით სივრცეში ბრძანებით 4 მილიარდი. ასე რომ არარეალურია. მაგრამ აქ ჩვენ ვიტყვით, ჩვენი შეკრული არის 200. შეასრულა რომ აკეთებს ამას O of N არის ჩვენ კიდევ მასივი მოუწოდა ითვლის of ზომა იკვრება. ასე რომ, რეალურად, ეს არის კომბინაცია, რომელიც - მე რეალურად არ ვიცი, თუ Clang აკეთებს ამას. მაგრამ gcc სულ ცოტა - I'm ვთქვათ Clang ს ძალიან - ამ მხოლოდ ინიციალიზაცია მთელი მასივი იყოს 0S. ასე რომ, თუ არ გსურთ, რომ, მაშინ შემეძლო ცალკე გააკეთოს (int i = 0; I <Bound, მე + +) და ითვლის [i] = 0; ასე რომ ახლა ყველაფერი ინიციალიზაცია რომ 0. მე iterate მეტი ჩემი მასივი, და რა ვარ აკეთებს არის მე დათვლის რიგი ყოველ - მოდი ქვემოთ აქ. ჩვენ გვყავს 4, 15, 16, 50, 8, 23, 42, 108. რა მე დათვლის პროცესი ხმების დამთხვევა თითოეული იმ ელემენტებს. მოდით რეალურად დაამატოთ წყვილი მეტი აქ ზოგიერთი მეორდება. ამიტომ ღირებულება გვაქვს აქ, ღირებულება, რომელიც იქნება array [i]. ამიტომ Val შეიძლება იყოს 4 ან 8 ან რასაც. და ახლა მე დათვლის რამდენი, რომ ღირებულება მე ვნახე, ასე ითვლის [Val] + +; ამის შემდეგ კეთდება, ითვლის აპირებს გამოიყურებოდეს მსგავსი რამ 0001. მოდით ითვლის [Val] - ვალდებული + 1. 

ახლა ეს მხოლოდ გათვალისწინებით იმისა, რომ ჩვენ დაწყებული 0. ასე რომ, თუ 200 იქნება ჩვენი ყველაზე დიდი რაოდენობის, მაშინ 0 დან 200 არის 201 რამ. ასე რომ ითვლის, იგი ყველაფერს ჰგავს 00001, რადგან ჩვენ გვაქვს ერთი 4. მაშინ გვექნება 0001, სადაც ჩვენ გვექნება 1 მე -8 მაჩვენებელი რაოდენობა. ჩვენ გვექნება 2 წელს 23 მაჩვენებელი რაოდენობა. ჩვენ გვექნება 2 წელს 42 მაჩვენებელი რაოდენობა. ასე რომ ჩვენ შეგვიძლია გამოვიყენოთ რაოდენობა. ამიტომ num_of_item = ითვლის [i]. და ასე თუ num_of_item არის 2, ეს ნიშნავს, რომ ჩვენ გვინდა ჩადეთ 2 რაოდენობის I ჩვენს დახარისხებული მასივი. ამიტომ, ჩვენ უნდა ტრეკზე, თუ რამდენად შორს ვართ შევიდა მასივი. ასე ინდექსი = 0. Array - მე უბრალოდ დაწერა. ითვლის - array [ინდექსი + +] = i; ის არის, რომ რაც მე მინდა? მე ვფიქრობ, რომ ის, რაც მე მინდა. დიახ, ეს გამოიყურება კარგი. Okay. ამიტომ ამჯამად ყველას გვესმოდეს რა მიზნით ჩემი ითვლის მასივი? იგი დათვლის რიგი შემთხვევები თითოეული ამ ნომრებზე. მაშინ მე iterating მეტი რომ ითვლის მასივი, და შ პოზიცია ითვლის მასივი არის რიგი მე რომ უნდა გამოჩნდება ჩემი დახარისხებული მასივი. ამიტომ ითვლის 4 იქნება 1 და ითვლის 8 დან იქნება 1, ითვლის 23 იქნება 2. ასე რომ, თუ რამდენი მათგანი მინდა INSERT INTO ჩემი დახარისხებული მასივი. მაშინ მე უბრალოდ რომ. მე ჩასმა num_of_item მე არის ჩემს დახარისხებული მასივი. 

კითხვები? და ა.შ. ერთხელ, ეს არის წრფივი, რადგან ჩვენ უბრალოდ iterating ამ ერთხელ, მაგრამ ასევე ხაზოვანი რა ეს ნომერი ხდება იყოს, ამიტომ მძიმედ დამოკიდებული, თუ რა თქვენი ბლოკნოტის არის. ერთად შეკრული, 200, რომ არ არის, რომ ცუდი. თუ თქვენი შეკრული იქნება 10,000, მაშინ რომ ცოტა უარესი, მაგრამ თუ თქვენი შეკრული იქნება 4 მილიარდი, რომ სრულიად არარეალური და ამ მასივი აპირებს უნდა იყოს ზომა 4 მილიარდი, რომელიც არარეალურია. ასე რომ, რომ. კითხვები? [Inaudible სტუდენტი საპასუხოდ] >> Okay. მე მივხვდი ერთ სხვა რამ, როდესაც ჩვენ გადის. ვფიქრობ პრობლემა იყო ლუკას და ალბათ თითოეული ჩვენ ვნახეთ. მე სრულიად დაავიწყდა. ერთადერთი, რაც მინდოდა კომენტარის გაკეთება, რომ როდესაც თქვენ საქმე რამ, როგორიცაა ინდექსები, თქვენ არასდროს ვხედავ ამ როდესაც თქვენ წერა ამისთვის მარყუჟის, მაგრამ ტექნიკურად, როდესაც თქვენ საქმე ამ მაჩვენებლების, თქვენ უნდა საკმაოდ ბევრი ყოველთვის გაუმკლავდეთ ხელმოუწერელი რიცხვებით. მიზეზი არის ის, როდესაც თქვენ საქმე ხელმოწერილი რიცხვებით, ასე რომ, თუ თქვენ გაქვთ 2 ხელმოწერილი რიცხვებით და დაამატოთ ისინი ერთად და მათ დასრულდება მდე ძალიან დიდი, მაშინ დასრულდება up ერთად უარყოფითი რიცხვი. ასე რომ სწორედ ეს რიცხვი overflow არის. 

თუ დავამატო 2 მილიარდი და 1 მილიარდი, მე დასრულდება მდე ნეგატიური 1 მილიარდი. ასე რიცხვებით მუშაობა კომპიუტერი. ასე რომ პრობლემა გამოყენებით - სწორედ ჯარიმის გარდა, თუ დაბალი მოხდება იქნება 2 მილიარდი და ხდება იყოს 1 მილიარდი, მაშინ ეს იქნება უარყოფითი 1 მილიარდი და შემდეგ ჩვენ ვაპირებთ გაყოფა, რომ 2 და დასრულდება მდე უარყოფითი 500 მილიონი. ასე რომ, ეს მხოლოდ საკითხის თუ მოხდება უნდა ეძებს მეშვეობით მასივი მილიარდობით რამ. მაგრამ თუ დაბალი + up ხდება overflow, მაშინ რომ პრობლემა. როგორც კი ჩვენ მათ ხელმოუწერელი, მაშინ 2 მილიარდი პლუს 1 მილიარდი არის 3 მილიარდი. 3 მილიარდი იყოფა 2 არის 1,5 მილიარდი. ამიტომ, როგორც კი ისინი ხელმოუწერელი, ყველაფერი სრულყოფილი. და ისე, რომ ასევე საკითხი, როდესაც თქვენ წერილობით თქვენი ამისთვის მარყუჟების, და ფაქტობრივად, ეს ალბათ აკეთებს ავტომატურად. ეს იქნება რეალურად მხოლოდ დაწეროთ თქვენ. ასე რომ, თუ ეს რიცხვი ძალიან დიდია, რომ მხოლოდ მთელი რიცხვი, მაგრამ ეს არ შეესაბამება ხელმოუწერელი რიცხვი, ეს იქნება დაწეროთ თქვენ, ასე ამიტომაც არასოდეს ნამდვილად გადაეყარონ საკითხი. თქვენ ხედავთ, რომ ინდექსის არასდროს იქნება უარყოფითი, და ამრიგად, როდესაც თქვენ iterating მეტი მასივი, შეგიძლიათ თითქმის ყოველთვის ვამბობ ხელმოუწერელი int i, მაგრამ თქვენ ნამდვილად არ უნდა. ყველაფერი იმუშავებს საკმაოდ ბევრი უბრალოდ ისევე. Okay. [ჩურჩული] რომელი საათია? ბოლო რამ მინდოდა, - და მე უბრალოდ მართლაც სწრაფი. თქვენ იცით, თუ როგორ ჩვენ # განსაზღვრავს ასე შეგვიძლია # define MAX როგორც 5 ან რაღაც? მოდით არ გააკეთებს MAX. # განსაზღვრავს დავალდებულებულნი 200. რაც გავაკეთეთ ადრე. რომელიც განსაზღვრავს მუდმივი, რომელიც მხოლოდ უნდა გადაწერა და pasted იქ, სადაც ჩვენ მოხდეს დაწერა იკვრება. 

ასე რომ ჩვენ შეგვიძლია რეალურად უფრო მეტი ერთად # განსაზღვრავს. ჩვენ შეგვიძლია # განსაზღვრავს ფუნქციებს. ისინი ნამდვილად არ ფუნქციებს, მაგრამ ჩვენ მოვუწოდებთ მათ ფუნქციებს. მაგალითი იქნება რაღაც MAX (x, y) განისაზღვრება როგორც (x <y? Y: X). Okay. ასე, რომ თქვენ უნდა შეეგუოს ternary ოპერატორის სინტაქსი, მაგრამ არის x ნაკლები Y? დაბრუნება Y, სხვაგან დაბრუნების x. ასე რომ თქვენ ხედავთ, შეგიძლიათ ამ ფუნქციის ცალკე, და ფუნქცია შეიძლება იყოს bool MAX იღებს 2 არგუმენტები, დააბრუნოს ეს. ეს არის ერთ ერთი ყველაზე საერთო პირობა ვხედავ გაკეთდეს მოსწონს ეს. ჩვენ მოვუწოდებთ მათ macros. ეს არის მაკრო. ეს არის მხოლოდ სინტაქსი იგი. თქვენ შეგიძლიათ დაწეროთ მაკრო გავაკეთოთ რაც გაგიხარდებათ. თქვენ ხშირად ვხედავ macros for გამართვის printfs და პერსონალი. ასე ტიპის printf, არსებობს სპეციალური მუდმივებზე C მოსწონს ხაზგასმა LINE ხაზგასასმელად, 2 ხაზს უსვამს ხაზს ხაზი, და არის კიდევ ვფიქრობ 2 ხაზს FUNC. ეს შეიძლება იგი. რამე მაგდაგვარს. იმ რამ შეიცვლება სახელით ფუნქცია ან ხმების ხაზი, რომ თქვენ შესახებ. ხშირად წერთ გამართვის printfs რომ ქვევით აქ შემეძლო მაშინ უბრალოდ დაწერეთ Debug და იქნება ბეჭდვა ხაზის ნომერი და ფუნქცია, რომ მე არ უნდა იყოს რომ იგი შეექმნა, რომ გამართვის განცხადებაში. და ასევე შეგიძლიათ ბეჭდვა სხვა რამ. ასე რომ ერთი რამ უნდა ფრთხილად არის თუ ემართება # განსაზღვრავს DOUBLE_MAX როგორც რაღაც 2 * Y-სა და 2 * x. ამიტომ სხვადსხვა მიზეზის გამო, თქვენ არ უნდა გავაკეთოთ, რომ ბევრი. ასე რომ ეს მაკრო. ეს არის რეალურად გატეხილი. მინდა მოვუწოდო მას ამით რაღაც DOUBLE_MAX (3, 6). მერე რა უნდა დაუბრუნდეს? [სტუდენტი] 12. დიახ, 12 უნდა დაუბრუნდეს და 12 ბრუნდება. 3 იღებს შეცვალა ამისთვის x, 6 იღებს შეცვალა ამისთვის Y, და ვბრუნდებით 2 * 6, რაც 12. ახლა რაც შეეხება ამ საკითხთან დაკავშირებით? რა უნდა დაბრუნდნენ? [სტუდენტი] 14. >> იდეალურ შემთხვევაში, 14. საკითხი არის ის, რომ როგორ hash განსაზღვრავს სამუშაოს, გახსოვდეთ ეს ლიტერატურული ასლი და პასტა საქართველოს საკმაოდ ბევრი ყველაფერი, ასე რომ ეს იქნება გაგებული, როგორც არის 3 ზე ნაკლები 1 plus 6, 2 ჯერ 1 plus 6, 2 ჯერ 3. 

ასე რომ, ამ მიზეზით თითქმის ყოველთვის გადაიტანოთ ყველაფერი ფრჩხილებში. ნებისმიერი ცვლადი თქვენ თითქმის ყოველთვის გადაიტანოთ ფრჩხილებში. არის შემთხვევები, სადაც თქვენ არ უნდა, ისევე როგორც მე ვიცი, რომ მე არ უნდა გავაკეთოთ, რომ აქ რადგან ნაკლები არის საკმაოდ ბევრი ყოველთვის მხოლოდ იმუშავებს, თუმცა, რომ შეიძლება არც კი იყოს ჭეშმარიტი. რამე სასაცილოა, როგორიც DOUBLE_MAX (1 == 2), მაშინ ეს ხდება მისაღებად შეცვალა 3 ზე ნაკლები 1 უდრის უდრის 2, და ასე შემდეგ ის აპირებს 3 ზე ნაკლები 1, ამჯამად რომ თანაბარი 2, რომელიც არ არის ის რაც ჩვენ გვინდა. ამიტომ, რათა ნებისმიერი ოპერატორის პრეცენდენტის პრობლემები, ყოველთვის გადაიტანოთ ფრჩხილებში. Okay. და ამით ყველაფერი, 5:30. თუ თქვენ გაქვთ რაიმე შეკითხვა pset, გვაცნობოთ. ეს უნდა იყოს სახალისო და ჰაკერული გამოცემა ასევე ბევრად უფრო რეალურია ვიდრე Hacker გამოცემა გასულ წელს, ასე რომ იმედი გვაქვს, რომ ბევრი თქვენგანი ცდილობენ. გასულ წელს იყო ძალიან დიდი. 

[CS50.TV]