1 00:00:00,000 --> 00:00:02,570 [Powered by Google Translate] [ნაწილი 3 - უფრო კომფორტული] 2 00:00:02,570 --> 00:00:05,070 [Rob Bowden - ჰარვარდის უნივერსიტეტი] 3 00:00:05,070 --> 00:00:07,310 >> [ეს არის CS50. - CS50.TV] 4 00:00:07,310 --> 00:00:12,700 >> ასე რომ პირველი კითხვა არის უცნაურად ფორმულირებული. 5 00:00:12,700 --> 00:00:17,480 GDB გაძლევთ "გამართვის" პროგრამით, მაგრამ, უფრო კონკრეტულად, რას მოგცემთ გავაკეთოთ? 6 00:00:17,480 --> 00:00:22,590 მე პასუხი, რომ ერთი, და მე არ ვიცი რა ზუსტად მოსალოდნელია, 7 00:00:22,590 --> 00:00:27,910 ამიტომ მე გამოცნობა ეს რაღაც გასწვრივ ხაზი იგი საშუალებას გაძლევთ ეტაპობრივად 8 00:00:27,910 --> 00:00:31,540 გავლა პროგრამის, ურთიერთქმედება ის, ენის ცვლადები, გავაკეთოთ ეს ყველაფერი - 9 00:00:31,540 --> 00:00:34,270 ძირითადად მთლიანად აკონტროლებენ აღსრულების პროგრამა 10 00:00:34,270 --> 00:00:38,410 და გაეცნონ ნებისმიერი ნაწილი აღსრულების პროგრამა. 11 00:00:38,410 --> 00:00:43,030 ასე რომ იმ თვისებების მოგცემთ გამართვის რამ. 12 00:00:43,030 --> 00:00:44,830 Okay. 13 00:00:44,830 --> 00:00:50,520 რატომ ბინარული ძებნის მოითხოვს, რომ მასივი იყოს დახარისხებული? 14 00:00:50,520 --> 00:00:53,360 ვის უნდა უპასუხოს, რომ? 15 00:00:56,120 --> 00:01:00,070 [სტუდენტი], რადგან ის არ იმუშავებს თუ ეს არ დახარისხებული. >> Yeah. [სიცილის] 16 00:01:00,070 --> 00:01:04,910 თუ ეს არ დახარისხებული, მაშინ შეუძლებელია გაყოფილი ის ნახევარზე 17 00:01:04,910 --> 00:01:07,850 და ვიცით, რომ ყველაფერი მარცხენა ნაკლებია და ყველაფერი სწორი 18 00:01:07,850 --> 00:01:10,490 მეტია შუა ღირებულება. 19 00:01:10,490 --> 00:01:12,790 ასე რომ ის უნდა დახარისხებული. 20 00:01:12,790 --> 00:01:14,170 Okay. 21 00:01:14,170 --> 00:01:17,570 რატომ არის ბუშტი sort in O of n კვადრატში? 22 00:01:17,570 --> 00:01:23,230 ვინმეს პირველი მინდა ძალიან სწრაფი მაღალი დონის მიმოხილვა რა ბუშტი დალაგების არის? 23 00:01:25,950 --> 00:01:33,020 [სტუდენტი] თქვენ ძირითადად გავლა თითოეულ ელემენტს და თქვენ შეამოწმოთ პირველი რამდენიმე ელემენტებს. 24 00:01:33,020 --> 00:01:37,150 თუ ისინი ვერ გამოვიდა, სადაც თქვენ სვოპ მათ, მაშინ შეამოწმოთ მომდევნო რამდენიმე ელემენტები და ასე შემდეგ. 25 00:01:37,150 --> 00:01:40,770 როდესაც თქვენ მივაღწიოთ ბოლოს, მაშინ თქვენ იცით, რომ ყველაზე დიდი ელემენტს განთავსებულია დასასრულს, 26 00:01:40,770 --> 00:01:42,750 ასე რომ თქვენ იგნორირება, რომ ერთი მაშინ გააგრძელოს გადის, 27 00:01:42,750 --> 00:01:48,490 და ყოველ ჯერზე თქვენ უნდა შეამოწმოთ ერთი ნაკლებად ელემენტს სანამ არ მიიღოს ცვლილებები არ. >> Yeah. 28 00:01:48,490 --> 00:01:58,470 ეს მოუწოდა bubble sort, რადგან თუ თქვენ Flip მასივი თავის მხრივ ამიტომ up და down, ვერტიკალური, 29 00:01:58,470 --> 00:02:03,100 მაშინ დიდი ღირებულებები ჩაიძიროს ბოლოში და პატარა ღირებულებები ბუშტი მდე დაბრუნება. 30 00:02:03,100 --> 00:02:05,210 ასე მას თავისი სახელი. 31 00:02:05,210 --> 00:02:08,220 და ჰო, უბრალოდ გავლა. 32 00:02:08,220 --> 00:02:11,190 თქვენ გაქვთ გადის მასივი, შევცვალე უფრო დიდი ღირებულება 33 00:02:11,190 --> 00:02:14,040 მიიღოს უდიდესი ღირებულებები ბოლოში. 34 00:02:14,040 --> 00:02:17,500 >> რატომ არის O of n კვადრატში? 35 00:02:18,690 --> 00:02:24,620 პირველი, ჯერ არავის მინდა ვთქვა, რატომ არის O of n კვადრატში? 36 00:02:24,620 --> 00:02:28,760 [სტუდენტი] გამო თითოეული გაუშვით მიდის N ჯერ. 37 00:02:28,760 --> 00:02:32,100 თქვენ შეგიძლიათ მხოლოდ დარწმუნდით, რომ თქვენ აღებული უმსხვილესი ელემენტს ყველა გზა down, 38 00:02:32,100 --> 00:02:35,230 მაშინ თქვენ უნდა გავიმეოროთ, რომ რაც შეიძლება ბევრი ელემენტები. >> Yeah. 39 00:02:35,230 --> 00:02:41,800 ასე რომ გაითვალისწინეთ რა დიდი O ნიშნავს და რა დიდი Omega საშუალებით. 40 00:02:41,800 --> 00:02:50,560 დიდი O ჰგავს ზედა შეკრული, თუ როგორ ნელა მას შეუძლია რეალურად აწარმოებს. 41 00:02:50,560 --> 00:02:58,990 ასე განაცხადა მისი O of n კვადრატში, ეს არ არის O of n ანდა იგი შეძლებს აწარმოებს 42 00:02:58,990 --> 00:03:02,640 წელს ხაზოვანი დროს, მაგრამ ეს O of n cubed 43 00:03:02,640 --> 00:03:06,390 რადგან ეს ესაზღვრება O of n cubed. 44 00:03:06,390 --> 00:03:12,300 თუ ეს ესაზღვრება O of n კვადრატში, მაშინ ის ესაზღვრება ასევე N cubed. 45 00:03:12,300 --> 00:03:20,280 სწორედ ამიტომ, n კვადრატში, და აბსოლუტური უარეს შემთხვევაში მას არ შეუძლია უკეთესად N კვადრატში, 46 00:03:20,280 --> 00:03:22,830 რის გამოც ის O მიერ ენ კვადრატში. 47 00:03:22,830 --> 00:03:31,200 ასე, რომ ნახოთ უმნიშვნელო მათემატიკის როგორ საქმე აღმოჩნდება N კვადრატში, 48 00:03:31,200 --> 00:03:40,530 თუ ჩვენ გვაქვს ხუთი რამ ჩვენს სიაში, პირველად რამდენი სვოპების შეგვეძლო პოტენციურად მოგიწევთ 49 00:03:40,530 --> 00:03:47,170 რათა მიიღოთ ამ? მოდით რეალურად მხოლოდ - 50 00:03:47,170 --> 00:03:52,040 რამდენი სვოპების მივდივართ ჰქონდეს, რათა პირველ პერსპექტივაში of bubble sort მეშვეობით მასივი? 51 00:03:52,040 --> 00:03:53,540 [სტუდენტი] n - 1. >> Yeah. 52 00:03:53,540 --> 00:03:58,340 >> თუ არსებობს 5 ელემენტები, ჩვენ ვაპირებთ მოგიწევთ n - 1. 53 00:03:58,340 --> 00:04:01,100 მერე მეორე რამდენი სვოპების მივდივართ რომ უნდა გააკეთოთ? 54 00:04:01,100 --> 00:04:03,440 [სტუდენტი] N - 2. >> Yeah. 55 00:04:03,440 --> 00:04:11,640 და მესამე იქნება N - 3, ხოლო შემდეგ მოხერხებულობის მე დაწერს ბოლო ორი 56 00:04:11,640 --> 00:04:15,270 როგორც მაშინ ჩვენ ვაპირებთ მოგიწევთ 2 გაცვლებს და 1 swap. 57 00:04:15,270 --> 00:04:19,899 ვფიქრობ ბოლო ერთი შეიძლება იყოს ან არ რეალურად უნდა მოხდეს. 58 00:04:19,899 --> 00:04:22,820 არის თუ არა swap? მე არ ვიცი. 59 00:04:22,820 --> 00:04:26,490 ასე რომ ეს არის სულ რაოდენობით გაცვლებს ან თუნდაც შედარებები თქვენ უნდა გააკეთოთ. 60 00:04:26,490 --> 00:04:29,910 მაშინაც კი, თუ თქვენ არ სვოპ, თქვენ კვლავ უნდა შეადაროთ ღირებულებებს. 61 00:04:29,910 --> 00:04:33,910 ასე რომ N - 1 შედარებები პირველ პერსპექტივაში მეშვეობით მასივი. 62 00:04:33,910 --> 00:04:42,050 თუ თქვენ rearrange ეს ყველაფერი, მოდით რეალურად ხდის, ექვსი რამ ასე რამ დააწყობს up ლამაზად, 63 00:04:42,050 --> 00:04:44,790 და მაშინ მე გავაკეთებ 3, 2, 1. 64 00:04:44,790 --> 00:04:49,910 ასე რომ მხოლოდ rearranging ეს თანხები, ჩვენ გვინდა, რომ რამდენი შედარებები ჩვენ 65 00:04:49,910 --> 00:04:52,700 მთელ ალგორითმი. 66 00:04:52,700 --> 00:04:56,550 ასე რომ, თუ ჩვენ მოუტანს ეს ბიჭები ქვემოთ აქ, 67 00:04:56,550 --> 00:05:07,470 მაშინ ჩვენ ჯერ კიდევ მხოლოდ შემაჯამებელი თუმცა ბევრი შედარებები იყო. 68 00:05:07,470 --> 00:05:13,280 მაგრამ თუ ჩვენ მთლიანობაში ეს და ჩვენ მთლიანობაში ეს და ჩვენ მთლიანობაში ეს, 69 00:05:13,280 --> 00:05:18,130 მაინც იგივე პრობლემა. ჩვენ უბრალოდ მთლიანობაში იმ კონკრეტულ ჯგუფებს. 70 00:05:18,130 --> 00:05:22,400 >> ახლა ჩვენ შემაჯამებელი 3 N-ს. ეს არ არის მხოლოდ 3 N-ს. 71 00:05:22,400 --> 00:05:27,650 ის ყოველთვის იქნება N / 2 N-ს. 72 00:05:27,650 --> 00:05:29,430 ასე რომ აქ ჩვენ ემართება აქვს 6. 73 00:05:29,430 --> 00:05:34,830 თუ ჩვენ გვქონდა 10 რამ, მაშინ ჩვენ შეგვიძლია ამის გაკეთება დაჯგუფება, 5 სხვადასხვა წყვილი რამ 74 00:05:34,830 --> 00:05:37,180 და დასრულდება up ერთად N + N + N + N + N. 75 00:05:37,180 --> 00:05:45,840 ასე რომ თქვენ ყოველთვის მიიღებთ N / 2 N-ს, და ა.შ. ეს ჩვენ jot იგი აღმოჩნდება N კვადრატში / 2. 76 00:05:45,840 --> 00:05:48,890 და ა.შ. მიუხედავად იმისა, რომ ეს ფაქტორი ნახევარი, რაც ხდება მოსვლა 77 00:05:48,890 --> 00:05:54,190 გამო იმისა, რომ მეშვეობით თითოეულ iteration მეტი მასივი შევადარებთ 1 ნაკლები 78 00:05:54,190 --> 00:05:58,040 ასე რომ, თუ როგორ მივიღებთ დაახლოებით 2, მაგრამ იგი მაინც n კვადრატში. 79 00:05:58,040 --> 00:06:01,650 ჩვენ არ აინტერესებს მუდმივი ფაქტორი ნახევარში. 80 00:06:01,650 --> 00:06:07,760 ასე რომ ბევრი დიდი O პერსონალის მოსწონს ეს ეყრდნობა მხოლოდ სახის აკეთებს ამ სახის მათემატიკის, 81 00:06:07,760 --> 00:06:12,260 აკეთებს არითმეტიკული თანხები და გეომეტრიული სერიის პერსონალის, 82 00:06:12,260 --> 00:06:17,750 მაგრამ მათი უმრავლესობა ამ კურსში არიან საკმაოდ მარტივია. 83 00:06:17,750 --> 00:06:19,290 Okay. 84 00:06:19,290 --> 00:06:24,430 რატომ არის Insertion sort in Omega of N? რას ნიშნავს omega? 85 00:06:24,430 --> 00:06:27,730 [ორი სტუდენტი საუბრობდა ერთხელ - გაუგებარია] >> Yeah. 86 00:06:27,730 --> 00:06:30,630 Omega შეგიძლიათ წარმოიდგინოთ, რომ როგორც ქვედა შეკრული. 87 00:06:30,630 --> 00:06:36,550 >> ასე რომ რაც არ უნდა ეფექტური თქვენი Insertion დახარისხების ალგორითმი არის, 88 00:06:36,550 --> 00:06:41,810 მიუხედავად სიაში რომ გადავიდა, მას ყოველთვის აქვს შედარება მინიმუმ N რამ 89 00:06:41,810 --> 00:06:44,620 ან ის iterate მეტი N რამ. 90 00:06:44,620 --> 00:06:47,280 რატომ არის, რომ? 91 00:06:47,280 --> 00:06:51,190 [სტუდენტი] რადგან თუ სიაში უკვე დახარისხებული, მაშინ მეშვეობით პირველი iteration 92 00:06:51,190 --> 00:06:54,080 თქვენ შეგიძლიათ მხოლოდ გარანტიას, რომ პირველივე ელემენტს არის მაინც, 93 00:06:54,080 --> 00:06:56,490 და მეორე iteration შეგიძლიათ ერთადერთი გარანტია პირველი ორი 94 00:06:56,490 --> 00:07:00,010 რადგან არ ვიცით, რომ დანარჩენ სია დალაგებულია. >> Yeah. 95 00:07:00,010 --> 00:07:08,910 თუ გაივლის სრულიად დახარისხებული სია, სულ ცოტა, თქვენ უნდა წავიდეთ ყველა ელემენტები 96 00:07:08,910 --> 00:07:12,180 დაინახოს, რომ არაფერი უნდა იყოს გადავიდა გარშემო. 97 00:07:12,180 --> 00:07:14,720 ამიტომ გარდაცვალება სიაში და ამბობდა oh, ეს უკვე დახარისხებული, 98 00:07:14,720 --> 00:07:18,240 ეს შეუძლებელია, იცოდეთ ეს დახარისხებული სანამ თქვენ შეამოწმოთ თითოეულ ელემენტს 99 00:07:18,240 --> 00:07:20,660 დაინახოს, რომ ისინი დახარისხებული მიზნით. 100 00:07:20,660 --> 00:07:25,290 ასე რომ ქვედა შეკრული on Insertion დალაგების არის ომეგა of n. 101 00:07:25,290 --> 00:07:28,210 რა უარეს შემთხვევაში გაშვებული დრო შერწყმა დახარისხების, 102 00:07:28,210 --> 00:07:31,390 უარეს შემთხვევაში ყოფნა დიდი O ერთხელ? 103 00:07:31,390 --> 00:07:37,660 ასე რომ, უარეს შემთხვევაში სცენარი, თუ როგორ ამჯამად შერწყმა დალაგების აწარმოებს? 104 00:07:42,170 --> 00:07:43,690 [სტუდენტი] N შესვლა n. >> Yeah. 105 00:07:43,690 --> 00:07:49,990 უსწრაფესი ზოგადი დახარისხება ალგორითმები N შესვლა n. თქვენ არ შეგიძლიათ უკეთესად. 106 00:07:51,930 --> 00:07:55,130 >> არსებობს განსაკუთრებულ შემთხვევებში და, თუ ჩვენ გვაქვს დრო დღეს - მაგრამ ჩვენ ალბათ won't - 107 00:07:55,130 --> 00:07:59,330 ჩვენ ვხედავდით ერთი რომ აკეთებს უკეთესად N შესვლა n. 108 00:07:59,330 --> 00:08:04,050 მაგრამ ზოგადად შემთხვევაში, თქვენ ვერ უკეთესად N შესვლა n. 109 00:08:04,050 --> 00:08:09,680 და შერწყმის დალაგება ხდება იყოს ერთი თქვენ უნდა იცოდეს, ამ თქმა, რომ არის N შესვლა n. 110 00:08:09,680 --> 00:08:13,260 და ა.შ. ჩვენ რეალურად უნდა განხორციელების, რომ დღეს. 111 00:08:13,260 --> 00:08:18,070 და ბოლოს, არა უმეტეს სამი სასჯელს, რამდენად შეესაბამება შერჩევის დალაგების მუშაობს? 112 00:08:18,070 --> 00:08:20,370 ამჯამად ვინმე გვინდა პასუხის გაცემა, და მე დათვალეთ სასჯელი 113 00:08:20,370 --> 00:08:22,390 რადგან თუ მეტი 3 - 114 00:08:25,530 --> 00:08:28,330 ვინმეს გახსოვთ შერჩევის დალაგება? 115 00:08:31,280 --> 00:08:37,809 შერჩევა დალაგების ჩვეულებრივ საკმაოდ ადვილად დასამახსოვრებელი მხოლოდ სახელი. 116 00:08:37,809 --> 00:08:45,350 თქვენ უბრალოდ iterate მეტი მასივი, იპოვეთ რასაც უდიდესი მნიშვნელობა არის თუ პატარა - 117 00:08:45,350 --> 00:08:47,290 რასაც რათა თქვენ დახარისხება სისტემაში 118 00:08:47,290 --> 00:08:50,750 ასე ვთქვათ ჩვენ დახარისხება საწყისი პატარა რომ უდიდესი. 119 00:08:50,750 --> 00:08:55,250 თქვენ iterate მეტი მასივი, ეძებს რასაც მინიმალური ელემენტი, 120 00:08:55,250 --> 00:08:59,750 ამოირჩიეთ, ხოლო შემდეგ მხოლოდ სვოპ ის რაც პირველ რიგში. 121 00:08:59,750 --> 00:09:04,090 და მერე მეორე უვლის მასივი, გადახედეთ მინიმალური ელემენტს ერთხელ, 122 00:09:04,090 --> 00:09:07,490 ამოირჩიეთ, შემდეგ სვოპ იგი რა მეორე ადგილი დაიკავეს. 123 00:09:07,490 --> 00:09:10,650 ჩვენ უბრალოდ კრეფა და ვირჩევთ მინიმალური ღირებულებები 124 00:09:10,650 --> 00:09:16,050 და ჩასმა მათთვის წინაშე მასივი სანამ ეს დახარისხებული. 125 00:09:19,210 --> 00:09:21,560 კითხვები რომ? 126 00:09:21,560 --> 00:09:25,710 >> ეს აუცილებლად გამოჩნდება ფორმები თქვენ უნდა შეავსონ როცა თქვენ წარდგენის pset. 127 00:09:29,010 --> 00:09:32,360 იმ ძირითადად პასუხი იმ. 128 00:09:32,360 --> 00:09:34,230 Okay, ასე არის კოდირების პრობლემები. 129 00:09:34,230 --> 00:09:40,140 მე უკვე გააძევეს მეტი ელ - ერთი ვინმე არ მიიღოთ, რომ წერილი? Okay. 130 00:09:40,140 --> 00:09:46,630 მე უკვე გააძევეს მეტი ელექტრონული სივრცე, როგორიც ჩვენ ვაპირებთ იყოს გამოყენებით, 131 00:09:46,630 --> 00:09:52,120 და თუ თქვენ დააჭირეთ ჩემი სახელი - ასე ვფიქრობ მე ვაპირებ იყოს ბოლოში 132 00:09:52,120 --> 00:09:57,170 გამო უკან r - მაგრამ თუ თქვენ დააჭირეთ ჩემი სახელი დაინახავთ 2 ვერსიებს. 133 00:09:57,170 --> 00:10:02,650 ცვლილებათა 1 იქნება მე უკვე გადაწერილი და pasted კოდი შევიდა სივრცეები 134 00:10:02,650 --> 00:10:06,900 ამისთვის ძებნა რაც თქვენ ვაპირებთ უნდა განახორციელოს. 135 00:10:06,900 --> 00:10:10,540 და სარევიზიო 2 იქნება დალაგების რამ, რომ ჩვენ განახორციელოს ამის შემდეგ. 136 00:10:10,540 --> 00:10:15,770 ამიტომ დააკლიკეთ ჩემი ცვლილებათა 1 და მუშაობა იქიდან. 137 00:10:17,350 --> 00:10:22,060 და ახლა ჩვენ გვინდა განვახორციელოთ ორობითი ძებნა. 138 00:10:22,060 --> 00:10:26,470 >> ვინმეს გვინდა უბრალოდ მისცეს pseudocode მაღალი დონის განმარტება 139 00:10:26,470 --> 00:10:31,440 რასაც ჩვენ ვაპირებთ უნდა გავაკეთოთ ძებნის? Yeah. 140 00:10:31,440 --> 00:10:36,170 [სტუდენტი] თქვენ უბრალოდ მიიღოს შუა array და ვხედავ თუ თქვენ მას ეძებს 141 00:10:36,170 --> 00:10:38,650 ნაკლებია ან მეტია. 142 00:10:38,650 --> 00:10:41,080 და თუ ის ნაკლებია, მიდიხარ ნახევარი რომ ნაკლებად, 143 00:10:41,080 --> 00:10:44,750 და თუ ეს უფრო, მიდიხარ ნახევარი, რომ უფრო და თქვენ გავიმეორო, რომ სანამ არ უბრალოდ ერთი რამ. 144 00:10:44,750 --> 00:10:46,570 [Bowden] Yeah. 145 00:10:46,570 --> 00:10:51,320 გაითვალისწინეთ, რომ ჩვენი ნომრები მასივი უკვე დახარისხებული, 146 00:10:51,320 --> 00:10:57,190 და ა.შ. ეს იმას ნიშნავს, რომ ჩვენ შეგვიძლია ისარგებლოს და ჩვენ შეიძლება პირველი ჩეკი, 147 00:10:57,190 --> 00:11:00,390 okay, ვეძებ ნომერი 50. 148 00:11:00,390 --> 00:11:03,720 ასე, რომ შეიძლება წასვლას ახლო. 149 00:11:03,720 --> 00:11:07,380 ახლო რთულია განსაზღვრა, როდესაც ეს კი რაოდენობის ნივთები, 150 00:11:07,380 --> 00:11:10,820 მაგრამ მოდით უბრალოდ, ვამბობთ ჩვენ ყოველთვის truncate შუა. 151 00:11:10,820 --> 00:11:14,420 ასე რომ აქ გვაქვს 8 რამ, ასე ახლო იქნებოდა 16. 152 00:11:14,420 --> 00:11:17,330 ვეძებ 50, ისე 50 მეტია 16. 153 00:11:17,330 --> 00:11:21,310 ახლა შემიძლია ძირითადად მკურნალობა ჩემი მასივს როგორც ამ ელემენტებს. 154 00:11:21,310 --> 00:11:23,450 შემიძლია გადაყარეთ ყველაფერი 16 ზე. 155 00:11:23,450 --> 00:11:27,440 ახლა ჩემი მასივი მხოლოდ ამ 4 ელემენტები, და ვიმეორებ. 156 00:11:27,440 --> 00:11:31,910 ასეა, მაშინ მინდა მოვძებნოთ ახლო ისევ, რომელიც იქნება 42. 157 00:11:31,910 --> 00:11:34,730 42 ნაკლებია, ვიდრე 50, ასე, რომ შეიძლება გადაყარეთ ამ ორი ელემენტები. 158 00:11:34,730 --> 00:11:36,890 ეს არის ჩემი დარჩენილი მასივი. 159 00:11:36,890 --> 00:11:38,430 მე ვაპირებ მოვძებნოთ ახლო ერთხელ. 160 00:11:38,430 --> 00:11:42,100 ვფიქრობ 50 იყო ცუდი მაგალითი, რადგან მე ყოველთვის სროლა მოშორებით რამ მარცხენა 161 00:11:42,100 --> 00:11:48,280 მაგრამ ამავე ღონისძიების, თუ ვეძებ რაღაც 162 00:11:48,280 --> 00:11:52,100 და ეს ნაკლები ელემენტს მე გაკეთებული ეძებს, 163 00:11:52,100 --> 00:11:55,080 მაშინ მე ვაპირებ გადაყარეთ ყველაფერი უფლება. 164 00:11:55,080 --> 00:11:58,150 ახლა ჩვენ გვჭირდება, რომ განხორციელდეს, რომ. 165 00:11:58,150 --> 00:12:02,310 გაითვალისწინეთ, რომ ჩვენ უნდა გაიაროს ზომის. 166 00:12:02,310 --> 00:12:06,730 ჩვენ შეგვიძლია ასევე არ უნდა მყარი კოდი ზომა. 167 00:12:06,730 --> 00:12:11,640 ასე რომ, თუ ჩვენ დავაღწიოთ რომ # define - 168 00:12:19,630 --> 00:12:21,430 Okay. 169 00:12:21,430 --> 00:12:27,180 როგორ შემიძლია ლამაზად გაერკვნენ, რა ზომის ციფრები მასივი გაკეთებული არის? 170 00:12:27,180 --> 00:12:30,950 >> რამდენი ელემენტები არიან ნომრები მასივი? 171 00:12:30,950 --> 00:12:33,630 [სტუდენტი] ნომრები, ფრჩხილებში,. სიგრძე? 172 00:12:33,630 --> 00:12:36,600 [Bowden], რომ არ არსებობს C. 173 00:12:36,600 --> 00:12:38,580 გჭირდებათ. სიგრძე. 174 00:12:38,580 --> 00:12:42,010 კოლექტორები არ აქვს თვისებები, ასე რომ არ არსებობს სიგრძე ქონება მასივი 175 00:12:42,010 --> 00:12:45,650 რომ მხოლოდ მოგცემთ თუმცა ხანგრძლივი ხდება, რომ იყოს. 176 00:12:48,180 --> 00:12:51,620 [სტუდენტი] რამდენად ბევრი მეხსიერების მას და ყოფს მიერ რამდენად - >> Yeah. 177 00:12:51,620 --> 00:12:55,810 ასე როგორ შეიძლება ჩვენ ვხედავთ, თუ რამდენი მეხსიერება მას? >> [სტუდენტი] Sizeof. >> Yeah, sizeof. 178 00:12:55,810 --> 00:13:01,680 Sizeof არის ოპერატორი, რომ აპირებს დაბრუნებას ზომის ციფრები მასივი. 179 00:13:01,680 --> 00:13:10,060 და ეს იქნება თუმცა ბევრი რიცხვებით არსებობს ჯერ ზომა რიცხვი 180 00:13:10,060 --> 00:13:14,050 რადგან ეს არის ის, თუ რამდენად მეხსიერების სინამდვილეში მიღება. 181 00:13:14,050 --> 00:13:17,630 ასე რომ, თუ მინდა ხმების რამ მასივი, 182 00:13:17,630 --> 00:13:20,560 მაშინ მე ვაპირებ მინდა გაყავით მიერ ზომა რიცხვი. 183 00:13:22,820 --> 00:13:26,010 Okay. ასე რომ, რომელიც საშუალებას ჩემთვის გაივლის ზომის აქ. 184 00:13:26,010 --> 00:13:29,430 რატომაა გავლა ზომის ყველა? 185 00:13:29,430 --> 00:13:38,570 რატომ არ შემიძლია უბრალოდ აქ int size = sizeof (haystack) / sizeof (int)? 186 00:13:38,570 --> 00:13:41,490 რატომ ამ არ იმუშავებს? 187 00:13:41,490 --> 00:13:44,470 [სტუდენტი] ეს არ გლობალური ცვლადი. 188 00:13:44,470 --> 00:13:51,540 [Bowden] Haystack არსებობს და ჩვენ გადადის ნომრები haystack, 189 00:13:51,540 --> 00:13:54,700 და ეს არის ერთგვარი foreshadowing რა მოვა. Yeah. 190 00:13:54,700 --> 00:14:00,170 [სტუდენტი] Haystack მხოლოდ მინიშნება მას, ასე რომ დაბრუნდნენ რამდენად დიდი რომ მინიშნება არის. 191 00:14:00,170 --> 00:14:02,150 Yeah. 192 00:14:02,150 --> 00:14:09,000 მე ეჭვი ლექცია რომ თქვენ ვხედავთ დასტის ჯერჯერობით ნამდვილად, არა? 193 00:14:09,000 --> 00:14:11,270 ჩვენ უბრალოდ ლაპარაკობენ ამის შესახებ. 194 00:14:11,270 --> 00:14:16,090 ამიტომ დასტის არის სადაც ყველა თქვენი ცვლადები ვაპირებთ ინახება. 195 00:14:16,090 --> 00:14:19,960 >> ნებისმიერი მეხსიერების რომ გამოყოფილი ადგილობრივი ცვლადები ხდება დასტის, 196 00:14:19,960 --> 00:14:24,790 და თითოეული ფუნქციის იღებს საკუთარი სივრცე დასტის, საკუთარი დასტის ჩარჩო არის რასაც ის მოუწოდა. 197 00:14:24,790 --> 00:14:31,590 ასე რომ მთავარ აქვს თავისი დასტის ჩარჩო, და შიგნით რომ აპირებს არსებობს ამ ნომრებზე მასივი, 198 00:14:31,590 --> 00:14:34,270 და ეს იქნება საქართველოს ზომა sizeof (ციფრები). 199 00:14:34,270 --> 00:14:38,180 ის აპირებს ზომის ციფრები იყოფა ზომის ელემენტები, 200 00:14:38,180 --> 00:14:42,010 მაგრამ, რომ ყველა ცხოვრების განმავლობაში ძირითად ს დასტის ჩარჩო. 201 00:14:42,010 --> 00:14:45,190 როდესაც ჩვენ მოვუწოდებთ ძებნა, ძიება იღებს საკუთარი დასტის ჩარჩო, 202 00:14:45,190 --> 00:14:48,840 საკუთარი სივრცის შესანახად ყველა მისი ადგილობრივი ცვლადები. 203 00:14:48,840 --> 00:14:56,420 მაგრამ ეს არგუმენტები - ასე haystack არ არის ასლის მთელი მასივი. 204 00:14:56,420 --> 00:15:00,990 ჩვენ არ გაივლის მთელ მასივს როგორც ასლი შევიდა ძებნა. 205 00:15:00,990 --> 00:15:04,030 უბრალოდ გადის მინიშნება, რომ მასივი. 206 00:15:04,030 --> 00:15:11,470 ასე ძებნა შეუძლიათ ამ ნომრებზე მეშვეობით მითითება. 207 00:15:11,470 --> 00:15:17,100 დღემდე წვდომის რამ, რომ იცხოვრონ შიგნით ძირითადი მისი დასტის ჩარჩო, 208 00:15:17,100 --> 00:15:22,990 მაგრამ ძირითადად, როცა ჩვენ ვიღებთ, რათა მითითებები, რომელიც უნდა იყოს სულ მალე, 209 00:15:22,990 --> 00:15:24,980 ეს რა მითითებები. 210 00:15:24,980 --> 00:15:29,400 მითითებები მხოლოდ მითითება რამ, და შეგიძლიათ გამოიყენოთ პოინტერები წვდომისათვის რამ 211 00:15:29,400 --> 00:15:32,030 რომ მსოფლიოს სხვა რამ 'დასტის ფარგლებში. 212 00:15:32,030 --> 00:15:37,660 ასე რომ, მიუხედავად იმისა, ნომრები არის ადგილობრივი მთავარ, ჩვენ მაინც ვებგვერდზე მეშვეობით ამ მაჩვენებელმა. 213 00:15:37,660 --> 00:15:41,770 მაგრამ რადგან ეს მხოლოდ კურსორი და უბრალოდ მინიშნება, 214 00:15:41,770 --> 00:15:45,040 sizeof (haystack) უბრალოდ ბრუნდება ზომა მინიშნება თავად. 215 00:15:45,040 --> 00:15:47,950 ეს არ დააბრუნებს ზომა რამ ეს მიუთითებს. 216 00:15:47,950 --> 00:15:51,110 ეს არ დააბრუნებს ფაქტობრივი ზომის ციფრები. 217 00:15:51,110 --> 00:15:55,660 და ასე რომ, ეს არ იმუშავებს, როგორც ჩვენ გვსურს. 218 00:15:55,660 --> 00:15:57,320 >> კითხვები რომ? 219 00:15:57,320 --> 00:16:03,250 პოინტერები იქნება გადაიზარდა მნიშვნელოვნად მეტი გორის დეტალურად კვირის მოსვლა. 220 00:16:06,750 --> 00:16:13,740 და სწორედ ამიტომ ბევრი რამ, რომ ხედავთ, ყველაზე ძებნა რამ ან დალაგება რამ, 221 00:16:13,740 --> 00:16:16,990 ისინი თითქმის ყველა აპირებს უნდა მიიღოს ფაქტობრივი ზომა მასივი, 222 00:16:16,990 --> 00:16:20,440 რადგან C, არ ვიცით, რა ზომის მასივი. 223 00:16:20,440 --> 00:16:22,720 თქვენ უნდა ხელით მსგავ სისტემაში 224 00:16:22,720 --> 00:16:27,190 და ვერ ხელით გაივლის მთელ მასივი, რადგან თქვენ მხოლოდ გადადის მინიშნება 225 00:16:27,190 --> 00:16:30,390 და მას არ შეუძლია მიიღოს ზომა საწყისი მითითება. 226 00:16:30,390 --> 00:16:32,300 Okay. 227 00:16:32,300 --> 00:16:38,160 ახლა ჩვენ გვინდა განვახორციელოთ რა განემარტა ადრე. 228 00:16:38,160 --> 00:16:41,530 შეგიძლიათ იმუშაოთ მასზე ერთი წუთით, 229 00:16:41,530 --> 00:16:45,250 და თქვენ არ ფიქრი მისაღებად ყველაფერი შესანიშნავად 100% მუშაობს. 230 00:16:45,250 --> 00:16:51,410 უბრალოდ წერენ up ნახევარში pseudocode თუ როგორ ფიქრობთ, უნდა იმუშაოს. 231 00:16:52,000 --> 00:16:53,630 Okay. 232 00:16:53,630 --> 00:16:56,350 არ უნდა იყოს მთლიანად გაკეთდეს ამ ამჟამად. 233 00:16:56,350 --> 00:17:02,380 მაგრამ ჯერ არავის გრძნობდნენ თავს კომფორტულად რაც მათ აქამდე, 234 00:17:02,380 --> 00:17:05,599 მოსწონს რაღაც შეგვიძლია ვიმუშაოთ ერთად? 235 00:17:05,599 --> 00:17:09,690 ვინმეს გვინდა მოხალისე? თორემ შემთხვევით აირჩიოთ. 236 00:17:12,680 --> 00:17:18,599 იგი არ უნდა იყოს უფლება ნებისმიერი ზომის მაგრამ შეგვიძლია ცვლილებები შევიდა სამუშაო სახელმწიფო. 237 00:17:18,599 --> 00:17:20,720 [სტუდენტი] რა თქმა უნდა. >> Okay. 238 00:17:20,720 --> 00:17:27,220 ასე რომ შეგიძლიათ შეინახოთ გადასინჯვის დაწკაპვით პატარა Save ხატი. 239 00:17:27,220 --> 00:17:29,950 თქვენ Ramya, არა? >> [სტუდენტი] Yeah. >> [Bowden] Okay. 240 00:17:29,950 --> 00:17:35,140 ახლა შემიძლია თქვენს გადასინჯვის და ყველას შეუძლია დახევის up გადასინჯვის. 241 00:17:35,140 --> 00:17:38,600 და აქ ჩვენ გვაქვს - Okay. 242 00:17:38,600 --> 00:17:43,160 ამიტომ Ramya წავიდა ერთად რეკურსიული გამოსავალი, რომელიც ნამდვილად სწორი გადაწყვეტა. 243 00:17:43,160 --> 00:17:44,970 არსებობს ორი გზა შეგიძლიათ გააკეთოთ ეს პრობლემა. 244 00:17:44,970 --> 00:17:48,060 თქვენ შეგიძლიათ ან გავაკეთებთ iteratively ან რეკურსიული. 245 00:17:48,060 --> 00:17:53,860 ყველაზე პრობლემებს თქვენ ექმნებათ, რომ შეიძლება გაკეთდეს რეკურსიული ასევე შეიძლება გაკეთდეს iteratively. 246 00:17:53,860 --> 00:17:58,510 ასე რომ აქ ჩვენ გავაკეთეთ ეს რეკურსიული. 247 00:17:58,510 --> 00:18:03,730 >> ამჯამად ვინმე გვინდა განვსაზღვროთ, თუ რას ნიშნავს, რათა ფუნქცია რეკურსიული? 248 00:18:07,210 --> 00:18:08,920 [სტუდენტი] როდესაც თქვენ გაქვთ ფუნქცია მოვუწოდებთ თავად 249 00:18:08,920 --> 00:18:13,470 და შემდეგ მოვუწოდებთ თავად სანამ გამოდის ჭეშმარიტი და მართალია. >> Yeah. 250 00:18:13,470 --> 00:18:17,680 რეკურსიული ფუნქცია მხოლოდ ფუნქცია, რომელიც მოუწოდებს თავად. 251 00:18:17,680 --> 00:18:24,140 არსებობს სამი დიდი რამ, რომ რეკურსიული ფუნქცია უნდა ჰქონდეს. 252 00:18:24,140 --> 00:18:27,310 პირველი აშკარად, ის მოუწოდებს თავად. 253 00:18:27,310 --> 00:18:29,650 მეორე ბაზის შემთხვევაში. 254 00:18:29,650 --> 00:18:33,390 ასე რომ რაღაც მომენტში ფუნქცია სჭირდება შეჩერება მოუწოდებდა თავად, 255 00:18:33,390 --> 00:18:35,610 და ეს რა ბაზა შემთხვევაში არის. 256 00:18:35,610 --> 00:18:43,860 ასე რომ აქ ჩვენ ვიცით, რომ ჩვენ უნდა შეწყვიტოს, ჩვენ უარი უნდა თქვას ჩვენს ძებნა 257 00:18:43,860 --> 00:18:48,150 როდესაც დაწყება შეადგენს ბოლოს - და ჩვენ წავიდეთ მეტი რა უნდა ნიშნავდეს ეს. 258 00:18:48,150 --> 00:18:52,130 მაგრამ საბოლოოდ, ბოლო რაც მნიშვნელოვანია რეკურსიული ფუნქციების: 259 00:18:52,130 --> 00:18:59,250 ფუნქციები უნდა როგორღაც მიახლოება ბაზის შემთხვევაში. 260 00:18:59,250 --> 00:19:04,140 Like თუ თქვენ არ რეალურად განახლებაზე არაფერი გამოვა მეორე რეკურსიული ზარი, 261 00:19:04,140 --> 00:19:07,880 თუ თქვენ სიტყვასიტყვით უბრალოდ მოუწოდებდა ფუნქციის კვლავ იგივე არგუმენტები 262 00:19:07,880 --> 00:19:10,130 და არ გლობალური ცვლადები შეიცვალა ან არაფერი, 263 00:19:10,130 --> 00:19:14,430 თქვენ არასოდეს აღწევს ბაზის შემთხვევაში, ამ შემთხვევაში რომ ცუდია. 264 00:19:14,430 --> 00:19:17,950 ეს იქნება უსასრულო უკან და დასტის overflow. 265 00:19:17,950 --> 00:19:24,330 მაგრამ აქ ჩვენ ვხედავთ, რომ განახლება ხდება, რადგან ჩვენ განახლებაზე დაიწყებს + ბოლომდე / 2, 266 00:19:24,330 --> 00:19:28,180 ჩვენ განახლებაზე ბოლოს არგუმენტი აქ, ჩვენ განახლებაზე დაწყება არგუმენტი აქ. 267 00:19:28,180 --> 00:19:32,860 ასე რომ ყველა რეკურსიული მოუწოდებს ჩვენ განახლებაზე რაღაც. Okay. 268 00:19:32,860 --> 00:19:38,110 გნებავთ ფეხით us საშუალებით თქვენი გამოსავალი? >> დარწმუნებული. 269 00:19:38,110 --> 00:19:44,270 მე გამოყენებით SearchHelp ისე, რომ ყოველ ჯერზე მე ამ ფუნქციის ზარის 270 00:19:44,270 --> 00:19:47,910 მაქვს დაწყების სადაც მე ვეძებ მასივში და ბოლოს 271 00:19:47,910 --> 00:19:49,380 სადაც მე დიდი იმედით მასივი. 272 00:19:49,380 --> 00:19:55,330 >> ყოველ ნაბიჯზე, სადაც ეს ამბობდა ის შუა ელემენტს, რომელიც დაწყება + ბოლომდე / 2, 273 00:19:55,330 --> 00:19:58,850 ის არის, რომ ტოლია, რაც ჩვენ ვეძებთ? 274 00:19:58,850 --> 00:20:04,650 და თუ მას, მაშინ აღმოვაჩინეთ, მაგრამ ვფიქრობ, რომ იღებს გავიდა up დონეზე უკან. 275 00:20:04,650 --> 00:20:12,540 და თუ ეს არ არის მართალი, მაშინ ჩვენ შეამოწმოს თუ არა, რომ ახლო ღირებულება array ძალიან დიდი, 276 00:20:12,540 --> 00:20:19,320 ამ შემთხვევაში ჩვენ შევხედოთ მარცხენა ნახევარში მასივი მიერ აპირებს დასაწყისიდან შუა ინდექსი. 277 00:20:19,320 --> 00:20:22,710 და სხვაგვარად გავაკეთოთ ბოლომდე ნახევარი. 278 00:20:22,710 --> 00:20:24,740 [Bowden] Okay. 279 00:20:24,740 --> 00:20:27,730 რომ ხმები კარგი. 280 00:20:27,730 --> 00:20:36,640 Okay, ასე რამდენიმე რამ, და ფაქტობრივად, ეს არის ძალიან მაღალი დონის რამ 281 00:20:36,640 --> 00:20:41,270 რომ თქვენ არასოდეს უნდა იცოდეთ ამ თქმა უნდა, მაგრამ ეს სიმართლეა. 282 00:20:41,270 --> 00:20:46,080 რეკურსიული ფუნქციების, ყოველთვის მესმის, რომ ისინი ცუდი გარიგება 283 00:20:46,080 --> 00:20:51,160 რადგან თუ რეკურსიული დაირქვით ძალიან ბევრი ჯერ, თქვენ დასტის overflow 284 00:20:51,160 --> 00:20:54,990 რადგან, როგორც ვთქვი, ყველა ფუნქცია იღებს საკუთარი დასტის ჩარჩო. 285 00:20:54,990 --> 00:20:59,500 ასე რომ ყოველ მოწოდებას რეკურსიული ფუნქცია იღებს საკუთარი დასტის ჩარჩო. 286 00:20:59,500 --> 00:21:04,140 ასე რომ, თუ თქვენ გააკეთებთ 1,000 რეკურსიული მოუწოდებს, თქვენ 1,000 დასტის ფარგლებში, 287 00:21:04,140 --> 00:21:08,390 და სწრაფად თქვენ გამოიწვიოს მქონე ძალიან ბევრი დასტის ფარგლებში და რამ მხოლოდ შესვენება. 288 00:21:08,390 --> 00:21:13,480 ასე ამიტომ რეკურსიული ფუნქციების ზოგადად ცუდი. 289 00:21:13,480 --> 00:21:19,370 მაგრამ არსებობს ლამაზი subset of რეკურსიული ფუნქციების მოუწოდა tail-რეკურსიული ფუნქციების 290 00:21:19,370 --> 00:21:26,120 და ეს მოხდება, იყოს მაგალითი, სადაც თუ შემდგენელი შეამჩნევს 291 00:21:26,120 --> 00:21:29,920 უნდა, ვფიქრობ - ში Clang თუ მსგავ-O2 დროშა 292 00:21:29,920 --> 00:21:33,250 მაშინ შეამჩნია ეს კუდი რეკურსიული და მიიღოს რამ კარგი. 293 00:21:33,250 --> 00:21:40,050 >> ეს იქნება reuse იგივე დასტის ჩარჩო უსასრულოდ თითოეული რეკურსიული ზარი. 294 00:21:40,050 --> 00:21:47,010 და რადგან თქვენ იყენებთ იგივე დასტის ჩარჩო, თქვენ არ გჭირდებათ ფიქრი 295 00:21:47,010 --> 00:21:51,690 ოდესმე დააწყობს overflowing, და ამავე დროს, როგორც თქვენ დაწყებამდე განაცხადა, 296 00:21:51,690 --> 00:21:56,380 აქ კიდევ თქვენ დაბრუნებას მართალია, მაშინ ის დააბრუნებს ყველა ამ დასტის ფარგლებში 297 00:21:56,380 --> 00:22:01,740 და მე -10 ზარი SearchHelp აქვს დაბრუნდეს მე -9, აქვს დაბრუნებას მე -8. 298 00:22:01,740 --> 00:22:05,360 ასე რომ არ სჭირდება ხდება ფუნქციებია კუდი რეკურსიული. 299 00:22:05,360 --> 00:22:13,740 და მერე რა ხდის ამ ფუნქციის კუდი რეკურსიული არის ცნობა ნებისმიერი მოცემული ზარი searchHelp 300 00:22:13,740 --> 00:22:18,470 რეკურსიული მოწოდება, რომ ეს მიღების არის რასაც ის დაბრუნების. 301 00:22:18,470 --> 00:22:25,290 ამიტომ პირველ ზარი SearchHelp, ჩვენ არც დაუყოვნებლივ დაბრუნებას ყალბი, 302 00:22:25,290 --> 00:22:29,590 დაუყოვნებლივ დაბრუნებას ასეა, ან ჩვენ რეკურსიული ზარი SearchHelp 303 00:22:29,590 --> 00:22:33,810 აქ რა ჩვენ დაბრუნების არის რა, რომ ზარის ბრუნდება. 304 00:22:33,810 --> 00:22:51,560 და ეს ვერ გავაკეთეთ ეს თითქოს ჩვენ აქ რაღაც int x = SearchHelp, დაბრუნების x * 2, 305 00:22:51,560 --> 00:22:55,440 რამოდენიმე შემთხვევითი ცვლილება. 306 00:22:55,440 --> 00:23:01,470 >> ახლა ამ რეკურსიული ზარის, ამ int x = SearchHelp რეკურსიული ზარი, 307 00:23:01,470 --> 00:23:05,740 აღარ არის კუდი რეკურსიული რადგანაც ეს ფაქტიურად ამჯამად გვაქვს დასაბრუნებელი 308 00:23:05,740 --> 00:23:10,400 თავში წინა დასტის ჩარჩო ასე რომ წინა ზარი ფუნქცია 309 00:23:10,400 --> 00:23:13,040 შეიძლება მაშინ რაღაც ერთად დაბრუნებული მნიშვნელობა. 310 00:23:13,040 --> 00:23:22,190 ასე რომ, ეს არ არის კუდი რეკურსიული, მაგრამ რა გვქონდა ადრე არის ლამაზად კუდი რეკურსიული. Yeah. 311 00:23:22,190 --> 00:23:27,000 [სტუდენტი] არ უნდა მეორე ბაზის შემთხვევაში მოწმდება პირველი 312 00:23:27,000 --> 00:23:30,640 რადგან შეიძლება იყოს სიტუაცია, სადაც როცა თქვენ გაიაროს ეს არგუმენტი 313 00:23:30,640 --> 00:23:35,770 თქვენ არ დაიწყოს = ბოლოს, მაგრამ ისინი ნემსი ღირებულება. 314 00:23:35,770 --> 00:23:47,310 შეკითხვა ვერ ჩვენ გადაეყარონ შემთხვევაში ბოლომდე არის ნემსი ღირებულება 315 00:23:47,310 --> 00:23:52,000 ან დაიწყოს = ბოლომდე, შესაბამისად, დაიწყოს = ბოლომდე 316 00:23:52,000 --> 00:23:59,480 და თქვენ არ რეალურად შემოწმდება, რომ კონკრეტული ღირებულება არ არის, 317 00:23:59,480 --> 00:24:03,910 შემდეგ დაიწყება + ბოლომდე / 2 არის მხოლოდ იქნება იგივე ღირებულება. 318 00:24:03,910 --> 00:24:07,890 მაგრამ ჩვენ უკვე დაბრუნდა ცრუ და ჩვენ არასოდეს რეალურად შემოწმდება ღირებულება. 319 00:24:07,890 --> 00:24:14,240 ამრიგად, სულ მცირე, პირველ ზარი, თუ ზომა არის 0, მაშინ ჩვენ გვინდა დაბრუნების ცრუ. 320 00:24:14,240 --> 00:24:17,710 მაგრამ თუ ზომა არის 1, მაშინ დაწყება არ აპირებს თანაბარი ბოლომდე, 321 00:24:17,710 --> 00:24:19,820 და ჩვენ მინიმუმ შეამოწმოთ ერთ ელემენტს. 322 00:24:19,820 --> 00:24:26,750 მაგრამ, ვფიქრობ, თქვენ უფლება, რომ ჩვენ შეგვიძლია დასრულდება up in შემთხვევაში დაიწყება + ბოლომდე / 2, 323 00:24:26,750 --> 00:24:31,190 დაწყება დამთავრდა თუ არა იგივე, რაც დაწყება + ბოლომდე / 2, 324 00:24:31,190 --> 00:24:35,350 მაგრამ ჩვენ არასოდეს რეალურად შემოწმდება რომ ელემენტს. 325 00:24:35,350 --> 00:24:44,740 >> ასე რომ, თუ ჩვენ პირველად ჩეკი არის შუა ელემენტს ღირებულების ჩვენ ვეძებთ, 326 00:24:44,740 --> 00:24:47,110 მაშინ ჩვენ შეგვიძლია დაუყოვნებლივ დაბრუნებას ჭეშმარიტი. 327 00:24:47,110 --> 00:24:50,740 Else თუ ისინი თანაბარი, მაშინ არ არსებობს წერტილი გრძელდება 328 00:24:50,740 --> 00:24:58,440 რადგან ჩვენ უბრალოდ აპირებს განახლებული შემთხვევაში ჩვენ ერთ ელემენტს მასივი. 329 00:24:58,440 --> 00:25:01,110 თუ ეს ერთჯერადი ელემენტს არ არის ერთი ჩვენ ვეძებთ, 330 00:25:01,110 --> 00:25:03,530 მაშინ ყველაფერი არასწორია. Yeah. 331 00:25:03,530 --> 00:25:08,900 [სტუდენტი] ის არის, რომ მას შემდეგ, რაც ზომა რეალურად აღემატება რაოდენობის ელემენტების მასივი, 332 00:25:08,900 --> 00:25:13,070 არსებობს უკვე ოფსეტური - >> ასე იქნება ზომა - 333 00:25:13,070 --> 00:25:19,380 [სტუდენტი] Say თუ წყობა იყო ზომა 0, მაშინ SearchHelp რეალურად შევამოწმოთ haystack of 0 334 00:25:19,380 --> 00:25:21,490 პირველ ზარს. 335 00:25:21,490 --> 00:25:25,300 Array ზომის 0, ასე რომ 0 არის - >> Yeah. 336 00:25:25,300 --> 00:25:30,750 არსებობს კიდევ ერთი რამ, - ეს შეიძლება იყოს კარგი. მოდით ვფიქრობ. 337 00:25:30,750 --> 00:25:40,120 ასე რომ, თუ მასივი ჰქონდა 10 ელემენტებს და ახლო ერთი ჩვენ ვაპირებთ შევამოწმოთ არის ინდექსი 5, 338 00:25:40,120 --> 00:25:45,700 ამიტომ ჩვენ შემოწმების 5, და ვთქვათ ღირებულება ნაკლებია. 339 00:25:45,700 --> 00:25:50,720 ამიტომ ჩვენ სროლა ყველაფერი დაშორებით 5 Onward. 340 00:25:50,720 --> 00:25:54,030 ასე რომ დავიწყოთ + ბოლომდე / 2 იქნება ჩვენი ახალი ბოლომდე, 341 00:25:54,030 --> 00:25:57,450 ასე yeah, ის ყოველთვის აპირებს დარჩენას მიღმა ბოლოს მასივი. 342 00:25:57,450 --> 00:26:03,570 თუ ეს იმ შემთხვევაში, თუ ეს იყო კი ან უცნაური, მაშინ ჩვენ შეამოწმოთ, ვთქვათ, 4, 343 00:26:03,570 --> 00:26:05,770 მაგრამ ჩვენ მაინც სროლა მოშორებით - 344 00:26:05,770 --> 00:26:13,500 ამიტომ yeah, ბოლოს ყოველთვის იქნება მიღმა ფაქტობრივი ბოლოს მასივი. 345 00:26:13,500 --> 00:26:18,350 ამიტომ ელემენტები ჩვენ აქცენტი, ბოლოს ყოველთვის იქნება ერთი ამის შემდეგ. 346 00:26:18,350 --> 00:26:24,270 და თუ დაწყება არ ოდესმე თანაბარი ბოლოს, ჩვენ ვართ მასივი ზომა 0. 347 00:26:24,270 --> 00:26:35,600 >> სხვა რამ მე აზროვნება ჩვენ განახლებაზე დაწყება უნდა დაიწყოს + ბოლომდე / 2, 348 00:26:35,600 --> 00:26:44,020 ასე რომ, ეს საქმე რომ მე მქონე უბედურება ერთად, სადაც დაიწყება + ბოლომდე / 2 349 00:26:44,020 --> 00:26:46,820 არის ელემენტს ჩვენ შემოწმების. 350 00:26:46,820 --> 00:26:58,150 ვთქვათ ჩვენ გვქონდა ამ 10-ელემენტს მასივი. როგორიც არ უნდა იყოს. 351 00:26:58,150 --> 00:27:03,250 ასე რომ დავიწყოთ + ბოლომდე / 2 იქნება რაღაც მსგავსი ერთი, 352 00:27:03,250 --> 00:27:07,060 და თუ ეს ასე არ არის ღირებულება, ვთქვათ გვინდა განახლება. 353 00:27:07,060 --> 00:27:10,060 ღირებულება მეტია, ამიტომ ჩვენ გვინდა შევხედოთ ამ ნახევარში მასივი. 354 00:27:10,060 --> 00:27:15,910 მაშ როგორ ჩვენ განახლებაზე დაწყება, ჩვენ განახლებაზე დასაწყისიდან ახლა ამ ელემენტს. 355 00:27:15,910 --> 00:27:23,790 მაგრამ ეს შეიძლება კვლავ მუშაობენ, ან სულ მცირე, შეგიძლიათ გააკეთოთ დაწყება + ბოლომდე / 2 + 1. 356 00:27:23,790 --> 00:27:27,850 [სტუდენტი] თქვენ არ უნდა იყოს დაიწყოს + ბოლომდე [inaudible] >> Yeah. 357 00:27:27,850 --> 00:27:33,240 ჩვენ უკვე გადამოწმებული ელემენტს და იციან, არ ერთი ჩვენ ვეძებთ. 358 00:27:33,240 --> 00:27:36,800 ამიტომ, ჩვენ არ გვჭირდება განახლება დაწყება უნდა იყოს ამ ელემენტს. 359 00:27:36,800 --> 00:27:39,560 ჩვენ შეგვიძლია მხოლოდ გამოტოვოთ იგი და განაახლოთ დაიწყებს იყოს ამ ელემენტს. 360 00:27:39,560 --> 00:27:46,060 და იქ ოდესმე შემთხვევაში, ვთქვათ, რომ ეს იყო ბოლომდე, 361 00:27:46,060 --> 00:27:53,140 ასეა, მაშინ დაიწყება იქნებოდა ამ, დაიწყოს + ბოლომდე / 2 იქნება ეს, 362 00:27:53,140 --> 00:28:00,580 დაიწყოს + ბოლომდე - ჰო, მე ვფიქრობ, რომ შეიძლება დასრულდეს up in უსასრულო უკან. 363 00:28:00,580 --> 00:28:12,690 ვთქვათ უბრალოდ მასივი ზომა 2 ან მასივი ზომა 1. ვფიქრობ, ეს იმუშავებს. 364 00:28:12,690 --> 00:28:19,490 ასე გაკეთებული, დაწყება არის ის, რომ ელემენტს და ბოლომდე არის 1 მის ფარგლებს გარეთ. 365 00:28:19,490 --> 00:28:24,110 ასე ელემენტს, რომ ჩვენ ვაპირებთ შევამოწმოთ ეს ერთი, 366 00:28:24,110 --> 00:28:29,400 და მაშინ, როდესაც ჩვენ განაახლოთ დაწყება, ჩვენ განახლებაზე დაწყება უნდა იყოს 0 + 1/2, 367 00:28:29,400 --> 00:28:33,160 რომელიც აპირებს დასრულდება us უკან დაწყება მყოფი ამ ელემენტს. 368 00:28:33,160 --> 00:28:36,210 >> ამიტომ ჩვენ შემოწმების იმავე ელემენტს უსასრულოდ. 369 00:28:36,210 --> 00:28:43,310 ასე რომ, ეს საქმე, სადაც ყველა რეკურსიული ზარის უნდა რეალურად განაახლოთ რაღაც. 370 00:28:43,310 --> 00:28:48,370 ამიტომ, ჩვენ უნდა გავაკეთოთ დაწყება + ბოლომდე / 2 + 1, ანდა არსებობს შემთხვევაში 371 00:28:48,370 --> 00:28:50,710 სადაც ჩვენ რეალურად არ განახლებაზე დაწყება. 372 00:28:50,710 --> 00:28:53,820 ყველამ დაინახოს, რომ? 373 00:28:53,820 --> 00:28:56,310 Okay. 374 00:28:56,310 --> 00:29:03,860 ვინმეს აქვს კითხვები ამ გადაწყვეტა ან რაიმე სხვა კომენტარები? 375 00:29:05,220 --> 00:29:10,280 Okay. ვინმეს არ iterative გადაწყვეტა, რომ ჩვენ შეგვიძლია ყველა შევხედოთ? 376 00:29:17,400 --> 00:29:20,940 ხომ ჩვენ ყველა გავაკეთებთ რეკურსიული? 377 00:29:20,940 --> 00:29:25,950 ან ასევე ვფიქრობ, თუ თქვენ გაიხსნა hers, მაშინ შესაძლოა თქვენი ჩანაცვლების წინა. 378 00:29:25,950 --> 00:29:28,810 იგი ავტომატურად შენახვა? მე არ ვარ დადებითი. 379 00:29:35,090 --> 00:29:39,130 ვინმეს არ iterative? 380 00:29:39,130 --> 00:29:42,430 ჩვენ შეგვიძლია გავლა ერთად, თუ არ. 381 00:29:46,080 --> 00:29:48,100 იდეა იქნება იგივე. 382 00:30:00,260 --> 00:30:02,830 Iterative გადაწყვეტა. 383 00:30:02,830 --> 00:30:07,140 ჩვენ ვაპირებთ გვინდა ძირითადად იგივე იდეა 384 00:30:07,140 --> 00:30:16,530 სად გვინდა ტრეკზე ახალი ბოლომდე array და ახალი დაწყების მასივი 385 00:30:16,530 --> 00:30:18,510 და გავაკეთოთ, რომ მეტი და მეტი. 386 00:30:18,510 --> 00:30:22,430 და თუ რა ჩვენ შენახვა ტრეკზე როგორც დაწყება და ბოლომდე ოდესმე იკვეთება, 387 00:30:22,430 --> 00:30:29,020 მაშინ ჩვენ ვერ და ჩვენ შეგვიძლია დაბრუნების ცრუ. 388 00:30:29,020 --> 00:30:37,540 მაშ როგორ შემიძლია ამის გაკეთება? ვინმეს აქვს წინადადებები ან კოდი ჩემთვის დახევის up? 389 00:30:42,190 --> 00:30:47,450 [სტუდენტი] Do ხოლო loop. >> Yeah. 390 00:30:47,450 --> 00:30:49,450 აპირებთ გსურთ loop. 391 00:30:49,450 --> 00:30:51,830 >> გქონდათ კოდი შემეძლო დახევის up ან რა იყო აპირებთ ვარაუდობენ? 392 00:30:51,830 --> 00:30:56,340 [სტუდენტი] ვფიქრობ ასე. >> ყველა უფლება. ეს ხდის რამ ადვილია. რა იყო თქვენი სახელი? 393 00:30:56,340 --> 00:30:57,890 [სტუდენტი] Lucas. 394 00:31:00,140 --> 00:31:04,190 ცვლილებათა 1. Okay. 395 00:31:04,190 --> 00:31:13,200 დაბალი არის, რაც ჩვენ მოუწოდა დაიწყოს. 396 00:31:13,200 --> 00:31:17,080 Up დიდი ხნის არ არის, რაც ჩვენ მოუწოდა ბოლომდე ადრე. 397 00:31:17,080 --> 00:31:22,750 რეალურად, ბოლოს არის ფარგლებში მასივი. ეს ელემენტს უნდა გავითვალისწინოთ. 398 00:31:22,750 --> 00:31:26,890 იმდენად დაბალია არის 0, up არის ზომა მასივი - 1, 399 00:31:26,890 --> 00:31:34,780 და ახლა ჩვენ looping და ჩვენ შემოწმების - 400 00:31:34,780 --> 00:31:37,340 ვფიქრობ შეგიძლიათ გავლა იგი. 401 00:31:37,340 --> 00:31:41,420 რა იყო თქვენი აზროვნების მეშვეობით? Walk us საშუალებით თქვენი კოდი. 402 00:31:41,420 --> 00:31:49,940 [სტუდენტი] რა თქმა უნდა. შეხედეთ haystack ღირებულების საშუალო და შეადაროთ იგი ნემსი. 403 00:31:49,940 --> 00:31:58,520 ასე რომ, თუ ის აღემატება თქვენი ნემსი, შემდეგ გსურთ - Oh, რეალურად, რომ უნდა იყოს უკან. 404 00:31:58,520 --> 00:32:05,180 თქვენ ვაპირებთ გვინდა გადაყარეთ მარჯვენა ნახევარში, და ისე ჰო, უნდა იყოს გზა. 405 00:32:05,180 --> 00:32:08,830 [Bowden] ასე რომ, ეს უნდა იყოს ნაკლები? ის არის, რომ ის, რაც თქვენ თქვით? >> [სტუდენტი] Yeah. 406 00:32:08,830 --> 00:32:10,390 [Bowden] Okay. ნაკლებია. 407 00:32:10,390 --> 00:32:15,700 ასე რომ, თუ რა ჩვენ შევხედავთ მცირეა, რაც ჩვენ გვინდა, 408 00:32:15,700 --> 00:32:19,410 მაშინ ჰო, ჩვენ გვინდა გადაყარეთ მარცხენა ნახევარში, 409 00:32:19,410 --> 00:32:22,210 რაც იმას ნიშნავს, რომ ჩვენ განახლებაზე ყველაფერი ჩვენ გათვალისწინებით 410 00:32:22,210 --> 00:32:26,610 გადაადგილების დაბალი მარჯვნივ მასივი. 411 00:32:26,610 --> 00:32:30,130 ეს გამოიყურება კარგი. 412 00:32:30,130 --> 00:32:34,550 მე ვფიქრობ, რომ აქვს იგივე საკითხი, რომელიც ჩვენ განაცხადა ადრე, 413 00:32:34,550 --> 00:32:49,760 აქ თუ არის დაბალი 0 და 1, მაშინ დაბალი + up / 2 აპირებს შექმნას იქნება იგივე ერთხელ. 414 00:32:49,760 --> 00:32:53,860 >> და მაშინაც კი, თუ ეს ასე არ არის საქმე, ეს კიდევ უფრო ეფექტური სულ ცოტა 415 00:32:53,860 --> 00:32:57,630 უბრალოდ გადააგდებს ელემენტს ჩვენ უბრალოდ შევხედე, რომელიც ჩვენ ვიცით, არასწორია. 416 00:32:57,630 --> 00:33:03,240 იმდენად დაბალია + up / 2 + 1 - >> [სტუდენტი], რომ უნდა იყოს სხვა გზა. 417 00:33:03,240 --> 00:33:05,900 [Bowden] ან ეს უნდა იყოს - 1 და მეორე უნდა იყოს + 1. 418 00:33:05,900 --> 00:33:09,580 [სტუდენტი] და იქ უნდა იყოს ორმაგი ტოლობის ნიშანი. >> [Bowden] Yeah. 419 00:33:09,580 --> 00:33:11,340 [სტუდენტი] Yeah. 420 00:33:14,540 --> 00:33:15,910 Okay. 421 00:33:15,910 --> 00:33:21,280 და ბოლოს, ახლა რომ ჩვენ გვაქვს ეს + 1 - 1 რამ, 422 00:33:21,280 --> 00:33:31,520 არის იგი - ეს შესაძლოა არ იყოს - ეს არის ის ოდესმე შესაძლებელი დაბალი დასრულდება up ერთად ღირებულება აღემატება up? 423 00:33:35,710 --> 00:33:40,320 ვფიქრობ ერთადერთი გზა, რომელიც შეიძლება მოხდეს - შეიძლება თუ არა? >> [სტუდენტი] არ ვიცი. 424 00:33:40,320 --> 00:33:45,220 მაგრამ თუ იგი იღებს truncated და შემდეგ იღებს მინუს რომ 1 და შემდეგ - >> Yeah. 425 00:33:45,220 --> 00:33:47,480 [სტუდენტი] უმჯობესი შესაძლოა მიიღოთ არევა. 426 00:33:49,700 --> 00:33:53,940 მე ვფიქრობ, ეს უნდა იყოს კარგი მხოლოდ იმიტომ 427 00:33:53,940 --> 00:33:58,800 მას მოხვდნენ ქვედა ისინი უნდა იყოს თანასწორი, ვფიქრობ. 428 00:33:58,800 --> 00:34:03,070 მაგრამ თუ ისინი თანაბარი, მაშინ ჩვენ არ გავაკეთეთ, ხოლო loop დავიწყოთ 429 00:34:03,070 --> 00:34:06,670 და ჩვენ უბრალოდ იქნებოდა დაბრუნებული მნიშვნელობა. ამიტომ, მე ვფიქრობ, რომ ჩვენ კარგად არის. 430 00:34:06,670 --> 00:34:11,530 გაითვალისწინეთ, რომ მიუხედავად იმისა, რომ ეს პრობლემა აღარ არის რეკურსიული, 431 00:34:11,530 --> 00:34:17,400 მსგავსი იდეები ვრცელდება, სადაც ჩვენ ვხედავთ, თუ როგორ ეს ასე ადვილად lends თავად 432 00:34:17,400 --> 00:34:23,659 to რეკურსიული გამოსავალი ის ფაქტი, რომ ჩვენ უბრალოდ განახლებას ინდექსების უსასრულოდ, 433 00:34:23,659 --> 00:34:29,960 ჩვენ მიღების პრობლემა პატარა და პატარა, ჩვენ აქცენტი subset of მასივი. 434 00:34:29,960 --> 00:34:40,860 [სტუდენტი] თუ დაბალი არის 0 და 1, ისინი ორივე იყოს 0 + 1/2, რომელიც წავიდოდა 0, 435 00:34:40,860 --> 00:34:44,429 და მაშინ ერთი იქნება + 1, ერთი იქნება - 1. 436 00:34:47,000 --> 00:34:50,870 [სტუდენტი] სად ვიმყოფებით შემოწმების თანასწორობის? 437 00:34:50,870 --> 00:34:55,100 Like თუ ახლო ერთი ფაქტიურად ნემსი? 438 00:34:55,100 --> 00:34:58,590 ჩვენ არ ამჟამად აკეთებს, რომ? Oh! 439 00:35:00,610 --> 00:35:02,460 თუ it's - 440 00:35:05,340 --> 00:35:13,740 დიახ. ჩვენ არ შეგვიძლია უბრალოდ ტესტი ქვემოთ აქ იმიტომ ვთქვათ პირველი ახლო - 441 00:35:13,740 --> 00:35:16,430 [სტუდენტი] სინამდვილეში მინდა არ გადაყარეთ ბლოკნოტებს. 442 00:35:16,430 --> 00:35:20,220 ასე რომ, თუ თქვენ გადაყარეთ შეკრული, თქვენ უნდა შეამოწმეთ იგი პირველი ან რასაც. 443 00:35:20,220 --> 00:35:23,350 Ah. Yeah. >> [სტუდენტი] Yeah. 444 00:35:23,350 --> 00:35:29,650 ახლა ჩვენ დააგდეს დაშორებით ერთი ჩვენ გაკეთებული შევხედე, 445 00:35:29,650 --> 00:35:33,260 რაც იმას ნიშნავს, რომ ჩვენ ახლა გვჭირდება ასევე აქვს 446 00:35:33,260 --> 00:35:44,810 თუ (haystack [(დაბალი + up) / 2] == ნემსი), მაშინ ჩვენ შეგვიძლია იქნება TRUE. 447 00:35:44,810 --> 00:35:52,070 და თუ არა მე ზუსტად სხვაგან, ან უბრალოდ თუ, ეს ნიშნავს სიტყვასიტყვით იგივე 448 00:35:52,070 --> 00:35:57,110 რადგან ეს იქნებოდა დაბრუნებული ჭეშმარიტი. 449 00:35:57,110 --> 00:36:01,450 ამიტომ მე დააყენა სხვაგან თუ, მაგრამ არა აქვს მნიშვნელობა. 450 00:36:01,450 --> 00:36:10,440 >> ასე რომ სხვაგან თუ ეს, სხვას ეს, და ეს არის საერთო რამ გავაკეთო 451 00:36:10,440 --> 00:36:14,340 აქ თუნდაც ის შემთხვევაა, როდესაც ყველაფერი კარგი აქ, 452 00:36:14,340 --> 00:36:22,780 მოსწონს დაბალი არ შეიძლება მეტი up, ეს არ ღირს მსჯელობა იმის შესახებ, რომ მართალია. 453 00:36:22,780 --> 00:36:28,010 ასე, რომ თქვენ შეიძლება ასევე აცხადებენ, ხოლო დაბალი ნაკლებია ან ტოლი 454 00:36:28,010 --> 00:36:30,720 ან მაშინ, როცა დაბალი ნაკლებია, ვიდრე 455 00:36:30,720 --> 00:36:35,300 ასე რომ, თუ ისინი ოდესმე თანაბარი ან დაბალი ხდება გაიაროს up, 456 00:36:35,300 --> 00:36:40,130 მაშინ ჩვენ შეგვიძლია დაარღვიოს ამ loop. 457 00:36:41,410 --> 00:36:44,630 კითხვები, შეშფოთება, კომენტარი? 458 00:36:47,080 --> 00:36:49,270 Okay. ეს გამოიყურება კარგი. 459 00:36:49,270 --> 00:36:52,230 ახლა ჩვენ გვინდა გავაკეთოთ ჯიშია. 460 00:36:52,230 --> 00:37:04,030 თუ ჩვენ გადასვლა ჩემს მეორე ვერსიასთან, ჩვენ ვხედავთ ამ საერთო ნომრები, 461 00:37:04,030 --> 00:37:07,550 მაგრამ ახლა ისინი აღარ დახარისხებული მიზნით. 462 00:37:07,550 --> 00:37:12,840 და გვინდა განხორციელება დალაგების გამოყენებით ნებისმიერი ალგორითმი O of n შესვლა n. 463 00:37:12,840 --> 00:37:17,240 ასე რომ რაც ალგორითმი ფიქრობთ უნდა განახორციელოს აქ? >> [სტუდენტი] Merge ჯიშია. 464 00:37:17,240 --> 00:37:23,810 [Bowden] Yeah. შერწყმა დალაგების არის O (N შესვლა N), ისე, რომ ის, რასაც ჩვენ ვაპირებთ. 465 00:37:23,810 --> 00:37:26,680 და პრობლემა იქნება საკმაოდ მსგავსია, 466 00:37:26,680 --> 00:37:31,920 სადაც მას ადვილად lends თავს რეკურსიული გადაწყვეტა. 467 00:37:31,920 --> 00:37:35,580 ჩვენ შეგვიძლია ასევე ამუშავება iterative გამოსავალი თუ გვინდა, 468 00:37:35,580 --> 00:37:42,540 მაგრამ უკან იქნება ადვილი აქ და ჩვენ უნდა გავაკეთოთ უკან. 469 00:37:45,120 --> 00:37:49,530 ვფიქრობ ჩვენ გავლა შერწყმა დალაგების პირველი, 470 00:37:49,530 --> 00:37:54,280 თუმცა არსებობს lovely ვიდეო შერწყმა დალაგების უკვე. [სიცილის] 471 00:37:54,280 --> 00:37:59,780 ასე რომ შერწყმა დალაგების არსებობს - მე გაყვანაა იმდენად, რამდენადაც ეს ქაღალდი. 472 00:37:59,780 --> 00:38:02,080 ოჰ, მხოლოდ ერთი მარცხენა. 473 00:38:02,080 --> 00:38:03,630 ასე რომ შერწყმა. 474 00:38:08,190 --> 00:38:12,470 Oh, 1, 3, 5. 475 00:38:26,090 --> 00:38:27,440 Okay. 476 00:38:29,910 --> 00:38:33,460 Merge იღებს ორი დამოუკიდებელი მასივები. 477 00:38:33,460 --> 00:38:36,780 ინდივიდუალურად იმ ორი კოლექტორები ორივე დახარისხებული. 478 00:38:36,780 --> 00:38:40,970 ასე რომ, ეს მასივი, 1, 3, 5, დახარისხებული. ეს მასივი, 0, 2, 4, დახარისხებული. 479 00:38:40,970 --> 00:38:46,710 ახლა რა შერწყმა უნდა გავაკეთოთ არის დააკავშიროთ მათ ერთ მასივი, რომელიც თავად დახარისხებული. 480 00:38:46,710 --> 00:38:57,130 ასე რომ ჩვენ გვინდა მასივი ზომა 6 რომ აპირებს აქვს ამ ელემენტების შიგნით ეს 481 00:38:57,130 --> 00:38:59,390 წელს დახარისხებული მიზნით. 482 00:38:59,390 --> 00:39:03,390 >> ასე რომ, ჩვენ შეიძლება ისარგებლოს იმ ფაქტს, რომ ამ ორი კოლექტორები რომლებიც დალაგებულია 483 00:39:03,390 --> 00:39:06,800 ამის გაკეთება წელს ხაზოვანი დროს, 484 00:39:06,800 --> 00:39:13,510 ხაზოვანი ახლა მნიშვნელობა, თუ ამ მასივი ზომა x და ეს ზომა Y, 485 00:39:13,510 --> 00:39:20,970 მაშინ სულ ალგორითმი უნდა იყოს O (x + y). Okay. 486 00:39:20,970 --> 00:39:23,150 ასე წინადადებები. 487 00:39:23,150 --> 00:39:26,030 [სტუდენტი] ვერ დავიწყებთ მარცხნიდან? 488 00:39:26,030 --> 00:39:30,150 ასე რომ თქვენ დააყენა 0 ქვემოთ და შემდეგ 1 და შემდეგ აქ თქვენ დროს 2. 489 00:39:30,150 --> 00:39:33,320 ასე რომ სახის მოსწონს გაქვთ tab რომ გადასვლის უფლება. >> [Bowden] Yeah. 490 00:39:33,320 --> 00:39:41,070 ორივე ეს კოლექტორები თუ ჩვენ მხოლოდ ფოკუსირება leftmost ელემენტს. 491 00:39:41,070 --> 00:39:43,530 იმის გამო, რომ ორივე კოლექტორები რომლებიც დალაგებულია, ჩვენ ვიცით, რომ ეს 2 ელემენტები 492 00:39:43,530 --> 00:39:46,920 არის პატარა ელემენტები ორივე მასივი. 493 00:39:46,920 --> 00:39:53,500 ასე რომ, რაც იმას ნიშნავს, რომ 1 იმ 2 ელემენტები უნდა იყოს პატარა ელემენტს ჩვენს შერწყმული მასივი. 494 00:39:53,500 --> 00:39:58,190 ეს უბრალოდ ისე ხდება, რომ პატარა არის ერთი მარჯვენა ამ დროს. 495 00:39:58,190 --> 00:40:02,580 ამიტომ ჩვენ ვიღებთ 0, ჩადეთ ის მარცხენა რადგან 0 ნაკლებია, ვიდრე 1, 496 00:40:02,580 --> 00:40:08,210 ასე მიიღოს 0, ჩადეთ იგი ჩვენი პირველი პოზიცია, და შემდეგ ჩვენ განაახლოთ 497 00:40:08,210 --> 00:40:12,070 აქამდე ფოკუსირებული პირველ ელემენტს. 498 00:40:12,070 --> 00:40:14,570 და ახლა ჩვენ ვიმეორებთ. 499 00:40:14,570 --> 00:40:20,670 ახლა შევადარებთ 2 და 1. 1 არის პატარა, ამიტომ ჩვენ ჩადეთ 1. 500 00:40:20,670 --> 00:40:25,300 ჩვენ განაახლოთ მომცეთ აღვნიშნო, რომ ამ ბიჭს. 501 00:40:25,300 --> 00:40:33,160 ახლა ჩვენ გავაკეთებთ ერთხელ, ასე რომ 2. ეს განაახლებს, შევადარებთ ამ 2, 3. 502 00:40:33,160 --> 00:40:37,770 ეს განახლება, მაშინ 4 და 5. 503 00:40:37,770 --> 00:40:42,110 ასე რომ არის შერწყმა. 504 00:40:42,110 --> 00:40:49,010 >> იგი უნდა იყოს საკმაოდ აშკარაა, რომ ეს არის ხაზოვანი ახლა რადგან ჩვენ უბრალოდ მასშტაბით თითოეული ელემენტის ერთხელ. 505 00:40:49,010 --> 00:40:55,980 და ეს არის ყველაზე დიდი ნაბიჯი განხორციელების შერწყმა sort აკეთებს ამ. 506 00:40:55,980 --> 00:40:59,330 და ეს არ არის რთული. 507 00:40:59,330 --> 00:41:15,020 რამდენიმე რამ ფიქრი არის ვთქვათ ჩვენ შერწყმის 1, 2, 3, 4, 5, 6. 508 00:41:15,020 --> 00:41:30,930 ამ შემთხვევაში ჩვენ დასრულდება მდე წელს სცენარი, სადაც ეს ერთი იქნება პატარა, 509 00:41:30,930 --> 00:41:36,160 მაშინ ჩვენ განაახლოთ მაჩვენებელი, ამ ერთი იქნება პატარა, განაახლოთ, 510 00:41:36,160 --> 00:41:41,280 ამ ერთი პატარა, და ახლა თქვენ უნდა აღიაროს 511 00:41:41,280 --> 00:41:44,220 როდესაც თქვენ ფაქტიურად ამოიწურა ელემენტების შედარებით. 512 00:41:44,220 --> 00:41:49,400 მას შემდეგ, რაც ჩვენ უკვე გამოიყენება მთელი მასივი, 513 00:41:49,400 --> 00:41:55,190 ყველაფერი ამ array არის მხოლოდ ჩასმული შევიდა აქ. 514 00:41:55,190 --> 00:42:02,040 ასე რომ, თუ ჩვენ ოდესმე გადაეყარონ წერტილში, სადაც ჩვენი ერთი მასივები მთლიანად გაერთიანდა უკვე, 515 00:42:02,040 --> 00:42:06,510 მაშინ ჩვენ უბრალოდ მიიღოს ყველა ელემენტების სხვა array და ჩადეთ მათთვის ბოლომდე მასივი. 516 00:42:06,510 --> 00:42:13,630 ასე რომ ჩვენ შეგვიძლია მხოლოდ ჩადეთ 4, 5, 6. Okay. 517 00:42:13,630 --> 00:42:18,070 სწორედ ერთია ფრთხილად. 518 00:42:22,080 --> 00:42:26,120 განხორციელება, რომ უნდა იყოს ნაბიჯი 1. 519 00:42:26,120 --> 00:42:32,600 შერწყმა დასალაგებლად შემდეგ ეფუძნება, რომ ეს 2 ნაბიჯები, 2 სულელური ნაბიჯები. 520 00:42:38,800 --> 00:42:42,090 მოდით უბრალოდ მისცეს ამ მასივი. 521 00:42:57,920 --> 00:43:05,680 ასე რომ შერწყმა დახარისხების, ნაბიჯი 1 არის რეკურსიული შესვენება მასივი შევიდა halves. 522 00:43:05,680 --> 00:43:09,350 ასე გაყოფილი ამ მასივი შევიდა halves. 523 00:43:09,350 --> 00:43:22,920 ჩვენ გვყავს 4, 15, 16, 50 და 8, 23, 42, 108. 524 00:43:22,920 --> 00:43:25,800 და ახლა ჩვენ გავაკეთებთ ერთხელ და ჩვენ გაყოფილი ამ შევიდა halves. 525 00:43:25,800 --> 00:43:27,530 მე მხოლოდ ამის შესახებ ამ მხარეს. 526 00:43:27,530 --> 00:43:34,790 ასე 4, 15 და 16, 50. 527 00:43:34,790 --> 00:43:37,440 ჩვენ ყველაფერს გააკეთებს იგივე აქ. 528 00:43:37,440 --> 00:43:40,340 და ახლა ჩვენ გაყოფილი იგი halves ერთხელ. 529 00:43:40,340 --> 00:43:51,080 ჩვენ გვყავს 4, 15, 16, 50. 530 00:43:51,080 --> 00:43:53,170 ასე რომ ჩვენი ბაზის შემთხვევაში. 531 00:43:53,170 --> 00:44:00,540 ერთხელ კოლექტორები არის ზომა 1, მაშინ ჩვენ შეწყვიტოს ერთად გაყოფის შევიდა halves. 532 00:44:00,540 --> 00:44:03,190 >> ახლა რას ვაკეთებთ ამ? 533 00:44:03,190 --> 00:44:15,730 ჩვენ დასრულდება მდე ამ ასევე ჩაშლის შევიდა 8, 23, 42, და 108. 534 00:44:15,730 --> 00:44:24,000 ახლა რომ ჩვენ ამ ეტაპზე, ახლა დაიხევს ორი შერწყმა დალაგება მხოლოდ შერწყმის წყვილი რათა სიები. 535 00:44:24,000 --> 00:44:27,610 ასე რომ ჩვენ გვინდა შერწყმა ამ. ჩვენ უბრალოდ ვუწოდებთ შერწყმა. 536 00:44:27,610 --> 00:44:31,410 ჩვენ ვიცით, შერწყმა დაბრუნდება ამ წელს დახარისხებული მიზნით. 537 00:44:31,410 --> 00:44:33,920 4, 15. 538 00:44:33,920 --> 00:44:41,440 ახლა ჩვენ გვინდა შერწყმა ამ, და რომ დაბრუნდება სია იმ დახარისხებული მიზნით, 539 00:44:41,440 --> 00:44:44,160 16, 50. 540 00:44:44,160 --> 00:44:57,380 ჩვენ შერწყმა იმ - ვერ წერენ - 8, 23 და 42, 108. 541 00:44:57,380 --> 00:45:02,890 ამიტომ ჩვენ გვაქვს გაერთიანებული წყვილი ერთხელ. 542 00:45:02,890 --> 00:45:05,140 ახლა ჩვენ მხოლოდ შერწყმა ერთხელ. 543 00:45:05,140 --> 00:45:10,130 გაითვალისწინეთ, რომ თითოეული ეს სიები დალაგებულია თავისთავად, 544 00:45:10,130 --> 00:45:15,220 და მაშინ ჩვენ შეგვიძლია მხოლოდ შერწყმა ამ სიებს კიდევ სიაში ზომა 4 რომელიც დახარისხებული 545 00:45:15,220 --> 00:45:19,990 და შერწყმის ამ ორი სიები მისაღებად სიაში ზომა 4 რომ დალაგებულია. 546 00:45:19,990 --> 00:45:25,710 და ბოლოს, ჩვენ შეგვიძლია შერწყმა ამ ორი სიები ზომა 4 მისაღებად ერთ სიაში ზომა 8 რომ დალაგებულია. 547 00:45:25,710 --> 00:45:34,030 ასე, რომ ეს არის საერთო N შესვლა N, ჩვენ უკვე ვნახეთ, რომ შერწყმა არის წრფივი, 548 00:45:34,030 --> 00:45:40,390 ასე რომ, როდესაც ჩვენ საქმე შერწყმის ამ, ასე მოსწონს საერთო ღირებულება შერწყმა 549 00:45:40,390 --> 00:45:43,410 ამ ორი სიები მხოლოდ 2 რადგან - 550 00:45:43,410 --> 00:45:49,610 ან ისე, ეს O of n, მაგრამ n აქ მხოლოდ ამ 2 ელემენტებს, ამიტომ 2. 551 00:45:49,610 --> 00:45:52,850 და ამ 2 იქნება 2 და ამ 2 იქნება 2 და ამ 2 იქნება 2, 552 00:45:52,850 --> 00:45:58,820 ასე მასშტაბით ყველა შერწყმების, რომ ჩვენ უნდა გავაკეთოთ, ჩვენ დასრულდება მდე აკეთებს n. 553 00:45:58,820 --> 00:46:03,210 Like 2 + 2 + 2 + 2 არის 8, რომელიც N, 554 00:46:03,210 --> 00:46:08,060 ასე ღირებულება შერწყმის ამ კომპლექტი არის n. 555 00:46:08,060 --> 00:46:10,810 და შემდეგ იგივე აქ. 556 00:46:10,810 --> 00:46:16,980 ჩვენ შერწყმა ამ 2, მაშინ ეს 2 და ინდივიდუალურად ამ შერწყმა მიიღებს ოთხი ოპერაციები, 557 00:46:16,980 --> 00:46:23,610 ამ შერწყმა მიიღებს ოთხი ოპერაციების, მაგრამ კიდევ ერთხელ, შორის ყველა ჩამოთვლილს, 558 00:46:23,610 --> 00:46:29,030 ჩვენ დასრულდება მდე შერწყმის N სულ რამ, და ა.შ. ეს ნაბიჯი იღებს n. 559 00:46:29,030 --> 00:46:33,670 და ა.შ. თითოეულ დონეზე იღებს n ელემენტებს მიმდინარეობს გაერთიანდა. 560 00:46:33,670 --> 00:46:36,110 >> და რამდენი დონეზე არსებობს? 561 00:46:36,110 --> 00:46:40,160 თითოეულ დონეზე, ჩვენი მასივი იზრდება ზომა 2. 562 00:46:40,160 --> 00:46:44,590 აქ ჩვენი კოლექტორები არის ზომა 1, აქ ისინი საქართველოში ზომა 2, აქ ისინი of ზომა 4, 563 00:46:44,590 --> 00:46:46,470 და ბოლოს, ისინი საქართველოს ზომა 8. 564 00:46:46,470 --> 00:46:56,450 , რადგან ეს გააორმაგოს, იქ ვაპირებთ იყოს სულ შესვლა n ამ დონეზე. 565 00:46:56,450 --> 00:47:02,090 ამრიგად შესვლა N დონეზე, თითოეული დონის აღების N სულ ოპერაციები, 566 00:47:02,090 --> 00:47:05,720 მივიღებთ N შესვლა N ალგორითმი. 567 00:47:05,720 --> 00:47:07,790 კითხვები? 568 00:47:08,940 --> 00:47:13,320 არ ხალხი უკვე მიაღწია პროგრესს, თუ როგორ უნდა განახორციელოს ეს? 569 00:47:13,320 --> 00:47:18,260 არის ვინმე უკვე იმ სახელმწიფოში, სადაც მე შემიძლია მხოლოდ გაიყვანოს საკუთარი კოდი? 570 00:47:20,320 --> 00:47:22,260 მე შემიძლია მოგცეთ წუთი. 571 00:47:24,770 --> 00:47:27,470 ეს ერთი იქნება აღარ. 572 00:47:27,470 --> 00:47:28,730 უაღრესად გირჩევთ recur - 573 00:47:28,730 --> 00:47:30,510 თქვენ არ უნდა გავაკეთოთ უკან ამისთვის შერწყმა 574 00:47:30,510 --> 00:47:33,750 რადგან გავაკეთოთ უკან ამისთვის შერწყმა, თქვენ აპირებს უნდა გაიარონ bunch სხვადასხვა ზომის. 575 00:47:33,750 --> 00:47:37,150 თქვენ შეგიძლიათ, მაგრამ შემაშფოთებელი. 576 00:47:37,150 --> 00:47:43,720 მაგრამ უკან დაბრუნების მიზნით დალაგება თავისთავად საკმაოდ მარტივია. 577 00:47:43,720 --> 00:47:49,190 თქვენ უბრალოდ სიტყვასიტყვით მოვუწოდებთ დალაგების მარცხენა ნახევარში, დალაგება მარჯვენა ნახევარში. Okay. 578 00:47:51,770 --> 00:47:54,860 ვინმეს აქვს რამე შემიძლია დახევის დღემდე? 579 00:47:54,860 --> 00:47:57,540 ანდა მე მივცემ წუთი. 580 00:47:58,210 --> 00:47:59,900 Okay. 581 00:47:59,900 --> 00:48:02,970 ვინმეს აქვს რაიმე შეგვიძლია ვიმუშაოთ? 582 00:48:05,450 --> 00:48:09,680 ანდა ჩვენ მხოლოდ მუშაობა ამ და შემდეგ გაფართოებას იქიდან. 583 00:48:09,680 --> 00:48:14,050 >> ვინმეს აქვს მეტი, ვიდრე ეს რომ შემიძლია დახევის up? 584 00:48:14,050 --> 00:48:17,770 [სტუდენტი] Yeah. შეგიძლიათ დახევის up აფეთქდა. >> ყველა უფლება. 585 00:48:17,770 --> 00:48:19,730 დიახ! 586 00:48:22,170 --> 00:48:25,280 [სტუდენტი] იყო ბევრი პირობები. >> Oh, დახვრიტეს. შეგიძლიათ - 587 00:48:25,280 --> 00:48:28,110 [სტუდენტი] მე უნდა შეინახოთ. >> Yeah. 588 00:48:32,420 --> 00:48:35,730 ამიტომ ჩვენ გავაკეთებთ შერწყმა ცალკე. 589 00:48:35,730 --> 00:48:38,570 ოჰ, მაგრამ ეს არ არის, რომ ცუდი. 590 00:48:39,790 --> 00:48:41,650 Okay. 591 00:48:41,650 --> 00:48:47,080 ასე დალაგება თავისთავად მხოლოდ მოუწოდებდა mergeSortHelp. 592 00:48:47,080 --> 00:48:49,530 ავუხსნათ თუ რას აკეთებს mergeSortHelp. 593 00:48:49,530 --> 00:48:55,700 [სტუდენტი] MergeSortHelp საკმაოდ ღირს ორი ძირითადი ნაბიჯები, 594 00:48:55,700 --> 00:49:01,270 რომელიც დასალაგებლად ყოველ ნახევარში array და შემდეგ შერწყმა ორივე მათგანი. 595 00:49:04,960 --> 00:49:08,050 [Bowden] Okay, ასე მომეცი მეორე. 596 00:49:10,850 --> 00:49:13,210 ვფიქრობ, ეს - >> [სტუდენტი] მე უნდა - 597 00:49:17,100 --> 00:49:19,400 Yeah. მე გავიგე რამე. 598 00:49:19,400 --> 00:49:23,100 In შერწყმა, ვხვდები, რომ მე უნდა შევქმნათ ახალი მასივი 599 00:49:23,100 --> 00:49:26,530 იმიტომ, რომ მე ვერ გავაკეთეთ ადგილზე. >> დიახ. თქვენ არ შეგიძლიათ. სწორი. 600 00:49:26,530 --> 00:49:28,170 [სტუდენტი] ასე, რომ შევქმნათ ახალი მასივი. 601 00:49:28,170 --> 00:49:31,510 დამავიწყდა დასასრულს შერწყმა ხელახლა შეიცვალოს. 602 00:49:31,510 --> 00:49:34,490 Okay. ჩვენ გვჭირდება ახალი მასივი. 603 00:49:34,490 --> 00:49:41,000 In შერწყმა დახარისხების, ეს არის თითქმის ყოველთვის მართალია. 604 00:49:41,000 --> 00:49:44,340 ნაწილი ღირებულება უკეთესი ალგორითმი დროის ბრძენი 605 00:49:44,340 --> 00:49:47,310 თითქმის ყოველთვის სჭირდება გამოიყენოს უფრო მეტი მეხსიერება. 606 00:49:47,310 --> 00:49:51,570 ასე რომ აქ, არ აქვს მნიშვნელობა, თუ როგორ გავაკეთოთ შერწყმა დახარისხების, 607 00:49:51,570 --> 00:49:54,780 თქვენ აუცილებლად უნდა გამოვიყენოთ ზოგიერთი დამატებითი მეხსიერება. 608 00:49:54,780 --> 00:49:58,240 მან შექმნა ახალი მასივი. 609 00:49:58,240 --> 00:50:03,400 და მაშინ ამბობენ დასასრულს ჩვენ უბრალოდ უნდა კოპირება ახალი მასივი შევიდა ორიგინალური მასივი. 610 00:50:03,400 --> 00:50:04,830 [სტუდენტი] ვფიქრობ ასე, yeah. 611 00:50:04,830 --> 00:50:08,210 მე არ ვიცი, თუ, რომელიც მუშაობს თვალსაზრისით დათვლის მიერ მინიშნება ან რასაც - 612 00:50:08,210 --> 00:50:11,650 ჰო, ის იმუშავებს. >> [სტუდენტი] Okay. 613 00:50:20,620 --> 00:50:24,480 გსმენიათ ვცდილობთ გაშვებული ამ? >> [სტუდენტი] არა, არ გაუკეთებია. >> Okay. 614 00:50:24,480 --> 00:50:28,880 სცადეთ გაშვებული, და მაშინ მე ამაზე მეორე. 615 00:50:28,880 --> 00:50:35,200 [სტუდენტი] მე უნდა ჰქონდეს ყველა ფუნქციის პროტოტიპები და ყველაფერი, თუმცა, არა? 616 00:50:37,640 --> 00:50:40,840 ფუნქციის პროტოტიპები. ოჰ, შენ ნიშნავს, როგორიცაა - დიახ. 617 00:50:40,840 --> 00:50:43,040 დალაგების მოუწოდებს mergeSortHelp. 618 00:50:43,040 --> 00:50:47,390 >> ამიტომ იმისათვის, დალაგება მოვუწოდო mergeSortHelp, mergeSortHelp უნდა ან არ არის განსაზღვრული 619 00:50:47,390 --> 00:50:56,370 ადრე დალაგების ან ჩვენ უბრალოდ უნდა პროტოტიპი. გადააკოპირეთ და ჩასვით რომ. 620 00:50:56,370 --> 00:50:59,490 და ანალოგიურად, mergeSortHelp მოუწოდებს შერწყმა, 621 00:50:59,490 --> 00:51:03,830 მაგრამ შერწყმა არ არის დადგენილი, ამიტომ ჩვენ შეგვიძლია უბრალოდ ნება mergeSortHelp ვიცი 622 00:51:03,830 --> 00:51:08,700 რომ სწორედ შერწყმა აპირებს ჰგავს, და ეს რომ. 623 00:51:09,950 --> 00:51:15,730 ამიტომ mergeSortHelp. 624 00:51:22,770 --> 00:51:32,660 ჩვენ გვყავს საკითხი აქ, სადაც ჩვენ არ გვაქვს ბაზა შემთხვევაში. 625 00:51:32,660 --> 00:51:38,110 MergeSortHelp არის რეკურსიული, ამიტომ ნებისმიერი რეკურსიული ფუნქცია 626 00:51:38,110 --> 00:51:42,610 სჭირდება გარკვეული ბაზა საქმე იცით, როდესაც შეჩერება რეკურსიული მოუწოდებდა თავად. 627 00:51:42,610 --> 00:51:45,590 რა არის ჩვენი ბაზის შემთხვევაში იქნება აქ? Yeah. 628 00:51:45,590 --> 00:51:49,110 [სტუდენტი] თუ ზომა არის 1? >> [Bowden] დიახ. 629 00:51:49,110 --> 00:51:56,220 ასე რომ როგორც ჩვენ ვნახეთ უფლება არსებობს, ჩვენ შეწყვიტა გაყოფა კოლექტორები 630 00:51:56,220 --> 00:52:01,850 ერთხელ ჩვენ ჩასხდნენ კოლექტორები of ზომა 1, რომელიც აუცილებლად არიან დახარისხებული თავს. 631 00:52:01,850 --> 00:52:09,530 ასე რომ, თუ ზომა შეადგენს 1, ვიცით მასივი უკვე დახარისხებული, 632 00:52:09,530 --> 00:52:12,970 ამიტომ ჩვენ შეგვიძლია უბრალოდ დააბრუნოს. 633 00:52:12,970 --> 00:52:16,880 >> გაითვალისწინეთ, რომ ბათილად, ამიტომ ჩვენ არ დაბრუნდებიან არაფერი განსაკუთრებული, უბრალოდ, დაბრუნდნენ. 634 00:52:16,880 --> 00:52:19,580 Okay. ასე რომ ჩვენი ბაზის შემთხვევაში. 635 00:52:19,580 --> 00:52:27,440 ვფიქრობ ჩვენი ბაზის შემთხვევაში შეიძლება, თუ ჩვენ არ უნდა იყოს შერწყმის მასივი ზომა 0, 636 00:52:27,440 --> 00:52:30,030 ჩვენ ალბათ სურთ შეწყვიტონ რაღაც მომენტში, 637 00:52:30,030 --> 00:52:33,610 ამიტომ ჩვენ შეგვიძლია უბრალოდ, ვამბობთ ზომა არანაკლებ 2 ან ნაკლები ან ტოლია 1 638 00:52:33,610 --> 00:52:37,150 ასე, რომ ეს იმუშავებს ნებისმიერი array არის. 639 00:52:37,150 --> 00:52:38,870 Okay. 640 00:52:38,870 --> 00:52:42,740 ასე რომ ჩვენი ბაზის შემთხვევაში. 641 00:52:42,740 --> 00:52:45,950 ახლა გინდა ფეხით ჩვენს მეშვეობით შერწყმა? 642 00:52:45,950 --> 00:52:49,140 რა ყველა ამ შემთხვევაში ნიშნავს? 643 00:52:49,140 --> 00:52:54,480 აქ, ჩვენ უბრალოდ აკეთებს იგივე იდეას, - 644 00:52:56,970 --> 00:53:02,470 [სტუდენტი] მე უნდა იყოს ავლით ზომა ყველა mergeSortHelp მოუწოდებს. 645 00:53:02,470 --> 00:53:10,080 მე დასძინა ზომა როგორც დამატებითი პირველადი და ეს არ არსებობს, ისევე, როგორც ზომა / 2. 646 00:53:10,080 --> 00:53:16,210 [Bowden] Oh, ზომა / 2, ზომა / 2. >> [სტუდენტი] ჰო, და ასევე ზემოთ ფუნქციის ისევე. 647 00:53:16,210 --> 00:53:21,320 [Bowden] აქ? >> [სტუდენტი] უბრალოდ ზომა. >> [Bowden] Oh. ზომა, ზომა? >> [სტუდენტი] Yeah. 648 00:53:21,320 --> 00:53:23,010 [Bowden] Okay. 649 00:53:23,010 --> 00:53:26,580 ნება მომეცით ვფიქრობ, მეორე. 650 00:53:26,580 --> 00:53:28,780 ჩვენ გადაეყარონ საკითხი? 651 00:53:28,780 --> 00:53:33,690 ჩვენ ყოველთვის მკურნალობის მარცხენა როგორც 0. >> [სტუდენტი] ჯგუფი 652 00:53:33,690 --> 00:53:36,340 სწორედ არასწორი ძალიან. უკაცრავად. ეს უნდა იყოს დაწყება. Yeah. 653 00:53:36,340 --> 00:53:39,230 [Bowden] Okay. მომწონს, რომ უკეთესი. 654 00:53:39,230 --> 00:53:43,880 და დასასრული. Okay. 655 00:53:43,880 --> 00:53:47,200 ახლა გინდა ფეხით ჩვენს მეშვეობით შერწყმა? >> [სტუდენტი] Okay. 656 00:53:47,200 --> 00:53:52,150 მე უბრალოდ გავლით ამ ახალი მასივი, რომ მე შევქმენით. 657 00:53:52,150 --> 00:53:57,420 მისი ზომა არის ზომა ნაწილი მასივი, რომ ჩვენ გვინდა იყოს დახარისხებული 658 00:53:57,420 --> 00:54:03,460 და ცდილობს იპოვოს ელემენტს, რომ მე უნდა ჩაიდოს ახალი მასივი ნაბიჯი. 659 00:54:03,460 --> 00:54:10,140 ასე გავაკეთოთ, რომ, პირველი მე შემოწმების თუ მარცხენა ნახევარში მასივი აგრძელებს რაიმე მეტი ელემენტები, 660 00:54:10,140 --> 00:54:14,260 და თუ ეს არ მოხდა, მაშინ ქვევით რომ სხვაგან მდგომარეობა, რომელიც მხოლოდ ამბობს 661 00:54:14,260 --> 00:54:20,180 Okay, ეს უნდა იყოს სწორი მასივი, და ჩვენ დააყენა, რომ მიმდინარე ინდექსი newArray. 662 00:54:20,180 --> 00:54:27,620 >> და შემდეგ სხვაგვარად, მე შემოწმების თუ მარჯვენა მხარეს მასივი ასევე დასრულდა, 663 00:54:27,620 --> 00:54:30,630 ამ შემთხვევაში მე უბრალოდ დასვა მარცხენა. 664 00:54:30,630 --> 00:54:34,180 შესაძლოა, სწორედ ამით რეალურად არ იყოს საჭირო. მე არ ვარ დარწმუნებული. 665 00:54:34,180 --> 00:54:40,970 მაგრამ მაინც, ხოლო დანარჩენი ორი გამშვები რომელი ორი პატარა ქალაქ მარცხნივ ან მარჯვნივ. 666 00:54:40,970 --> 00:54:49,770 და ასევე ყოველ შემთხვევაში, მე დამატება რომელი placeholder I იყოს. 667 00:54:49,770 --> 00:54:52,040 [Bowden] Okay. 668 00:54:52,040 --> 00:54:53,840 რომელიც გამოიყურება კარგი. 669 00:54:53,840 --> 00:54:58,800 ვინმეს აქვს კომენტარი ან შეშფოთება ან კითხვები? 670 00:55:00,660 --> 00:55:07,720 ასე რომ ოთხი შემთხვევებში, რომ გვაქვს, რათა რამ შევიდა მხოლოდ კონკრეტდება - ან გამოიყურება ხუთი - 671 00:55:07,720 --> 00:55:13,100 მაგრამ იმის გათვალისწინებით, თუ რამდენად მარცხენა მასივი უკვე ამოიწურა რამ უნდა შერწყმა, 672 00:55:13,100 --> 00:55:16,390 თუ არა უფლება მასივი უკვე ამოიწურა რამ უნდა შერწყმა - 673 00:55:16,390 --> 00:55:18,400 მე მიუთითებს არაფერი. 674 00:55:18,400 --> 00:55:21,730 ასე თუ არა მარცხენა მასივი უკვე ამოიწურა რამ ან უფლება მასივი უკვე ამოიწურა რამ. 675 00:55:21,730 --> 00:55:24,320 ეს ის ორი შემთხვევა. 676 00:55:24,320 --> 00:55:30,920 ჩვენ ასევე გვჭირდება ტრივიალური შემთხვევაში თუ არა მარცხენა რამ არის ნაკლები ვიდრე სწორი. 677 00:55:30,920 --> 00:55:33,910 მაშინ ჩვენ გვინდა აირჩიოს მარცხენა რამ. 678 00:55:33,910 --> 00:55:37,630 იმ შემთხვევებში. 679 00:55:37,630 --> 00:55:40,990 ასე რომ, ეს იყო სწორი, ასე რომ, რომ. 680 00:55:40,990 --> 00:55:46,760 Array დაუტოვებიათ. ეს 1, 2, 3. Okay. ამიტომ yeah, ეს ის ოთხი რამ შეიძლება გსურთ. 681 00:55:50,350 --> 00:55:54,510 და ჩვენ არ წავიდეთ მეტი iterative გადაწყვეტა. 682 00:55:54,510 --> 00:55:55,980 არ ვურჩევთ - 683 00:55:55,980 --> 00:56:03,070 შერწყმა დალაგების არის მაგალითი ფუნქცია, რომელიც ორივე არ კუდი რეკურსიული, 684 00:56:03,070 --> 00:56:07,040 ეს არ არის ადვილი, რათა ის კუდი რეკურსიული, 685 00:56:07,040 --> 00:56:13,450 არამედ ეს არ არის ძალიან ადვილია, რათა ის iterative. 686 00:56:13,450 --> 00:56:16,910 ეს ძალიან მარტივია. 687 00:56:16,910 --> 00:56:19,170 ეს განხორციელებას შერწყმა დახარისხების, 688 00:56:19,170 --> 00:56:22,140 შერწყმა, არ აქვს მნიშვნელობა, თუ რას აკეთებთ, თქვენ აპირებს ააშენოს შერწყმა. 689 00:56:22,140 --> 00:56:29,170 >> ასე რომ შერწყმა დალაგების აგებული ზევით შერწყმა რეკურსიული მხოლოდ ამ სამი ხაზები. 690 00:56:29,170 --> 00:56:34,700 Iteratively, ეს უფრო შემაშფოთებელი და უფრო რთული ვიფიქროთ. 691 00:56:34,700 --> 00:56:41,860 მაგრამ შეამჩნია, რომ ეს არ კუდი რეკურსიული წლიდან mergeSortHelp - როდესაც ის მოუწოდებს თავად - 692 00:56:41,860 --> 00:56:46,590 იგი ჯერ კიდევ გავაკეთოთ რამ ამის შემდეგ რეკურსიული ზარის ბრუნდება. 693 00:56:46,590 --> 00:56:50,830 ასე რომ, ეს დასტის ჩარჩოში უნდა განაგრძოს არსებობას შემდეგაც კი მოუწოდებდა ამ. 694 00:56:50,830 --> 00:56:54,170 და მაშინ, როდესაც თქვენ დაარქვით, დასტის ჩარჩოში უნდა განაგრძოს არსებობს 695 00:56:54,170 --> 00:56:57,780 რადგან შემდეგაც კი ეს გამოძახილი, ჩვენ მაინც უნდა შერწყმა. 696 00:56:57,780 --> 00:57:01,920 და ეს nontrivial რათა ამ კუდი რეკურსიული. 697 00:57:04,070 --> 00:57:06,270 კითხვები? 698 00:57:08,300 --> 00:57:09,860 ყველა უფლება. 699 00:57:09,860 --> 00:57:13,400 ასე რომ დაუბრუნდეს დასალაგებლად - Oh, არსებობს ორი რამ მინდა ნახოთ. Okay. 700 00:57:13,400 --> 00:57:17,840 უკან დასალაგებლად, ჩვენ გავაკეთებთ ამ სწრაფად. 701 00:57:17,840 --> 00:57:21,030 ან ძებნის. დალაგება? დალაგება. Yeah. 702 00:57:21,030 --> 00:57:22,730 ბრუნდება დასაწყისი ჯიშია. 703 00:57:22,730 --> 00:57:29,870 ჩვენ გვინდა რომ შევქმნათ ალგორითმი რომ სახის მასივი გამოყენებით ნებისმიერი ალგორითმი 704 00:57:29,870 --> 00:57:33,660 წელს O of n. 705 00:57:33,660 --> 00:57:40,860 მაშ როგორ არის ეს შესაძლებელი? ვინმეს აქვს რაიმე სახის - 706 00:57:40,860 --> 00:57:44,300 მე მიანიშნა ადრე at - 707 00:57:44,300 --> 00:57:48,300 თუ ჩვენ შესახებ გასაუმჯობესებლად საწყისი N შესვლა n to O of n, 708 00:57:48,300 --> 00:57:51,450 ჩვენ გაუმჯობესდა ჩვენი ალგორითმი დროის ბრძენი, 709 00:57:51,450 --> 00:57:55,250 რაც იმას ნიშნავს, რას ვაპირებთ გვჭირდება შეადგინოს ამისთვის? 710 00:57:55,250 --> 00:57:59,520 [სტუდენტი] ფართი. >> Yeah. ჩვენ ვაპირებთ იყოს გამოყენებით მეტი სივრცე. 711 00:57:59,520 --> 00:58:04,490 და არც კი მხოლოდ მეტი სივრცე, ეს exponentially მეტი სივრცე. 712 00:58:04,490 --> 00:58:14,320 ამიტომ ვფიქრობ ამ ტიპის ალგორითმი ფსევდო რაღაც, ფსევდო polynom - 713 00:58:14,320 --> 00:58:18,980 ფსევდო - მე არ მახსოვს. ფსევდო რაღაც. 714 00:58:18,980 --> 00:58:22,210 მაგრამ ეს იმიტომ, რომ ჩვენ უნდა გამოვიყენოთ იმდენად სივრცეში 715 00:58:22,210 --> 00:58:28,610 რომ ეს მიღწევადია, მაგრამ არა რეალისტური. 716 00:58:28,610 --> 00:58:31,220 >> და როგორ უნდა მივაღწიოთ ამას? 717 00:58:31,220 --> 00:58:36,810 ჩვენ შეგვიძლია მივაღწიოთ ამ შემთხვევაში ჩვენ ვიძლევით გარანტიას, რომ რომელიმე კონკრეტულ ელემენტს მასივი 718 00:58:36,810 --> 00:58:39,600 ქვემოთ არის გარკვეული ზომით. 719 00:58:42,070 --> 00:58:44,500 მოდით უბრალოდ, ვამბობთ, რომ ზომა არის 200, 720 00:58:44,500 --> 00:58:48,130 ნებისმიერი ელემენტი მასივი ქვემოთ ზომა 200. 721 00:58:48,130 --> 00:58:51,080 და ეს არის ძალიან რეალისტური. 722 00:58:51,080 --> 00:58:58,660 თქვენ შეგიძლიათ ძალიან მარტივად აქვს მასივი, რომ თქვენ იცით, ყველაფერი ეს 723 00:58:58,660 --> 00:59:00,570 იქნება ნაკლები გარკვეული რაოდენობის. 724 00:59:00,570 --> 00:59:07,400 Like თუ გაქვთ აბსოლუტურად მასიური ვექტორი ან რამე 725 00:59:07,400 --> 00:59:11,810 მაგრამ თქვენ იცით, ყველაფერი იქნება შორის 0 და 5, 726 00:59:11,810 --> 00:59:14,790 მაშინ იქნება მნიშვნელოვნად უფრო სწრაფად ამის გაკეთება. 727 00:59:14,790 --> 00:59:17,930 და ბლოკნოტებს ნებისმიერ ელემენტებს არის 5, 728 00:59:17,930 --> 00:59:21,980 ასე რომ ეს შეკრული, რომ არის, თუ რამდენი მეხსიერება თქვენ უნდა გამოყენებით. 729 00:59:21,980 --> 00:59:26,300 ასე რომ ბლოკნოტებს არის 200. 730 00:59:26,300 --> 00:59:32,960 თეორიულად ყოველთვის არის შეკრული, რადგან მთელი რიცხვი უნდა იყოს მხოლოდ მდე 4 მილიარდი, 731 00:59:32,960 --> 00:59:40,600 მაგრამ ეს არარეალურია, რადგან მაშინ ჩვენ მინდა იყოს გამოყენებით სივრცეში 732 00:59:40,600 --> 00:59:44,400 ბრძანებით 4 მილიარდი. ასე რომ არარეალურია. 733 00:59:44,400 --> 00:59:47,060 მაგრამ აქ ჩვენ ვიტყვით, ჩვენი შეკრული არის 200. 734 00:59:47,060 --> 00:59:59,570 შეასრულა რომ აკეთებს ამას O of N არის ჩვენ კიდევ მასივი მოუწოდა ითვლის of ზომა იკვრება. 735 00:59:59,570 --> 01:00:10,470 ასე რომ, რეალურად, ეს არის კომბინაცია, რომელიც - მე რეალურად არ ვიცი, თუ Clang აკეთებს ამას. 736 01:00:11,150 --> 01:00:15,330 მაგრამ gcc სულ ცოტა - I'm ვთქვათ Clang ს ძალიან - 737 01:00:15,330 --> 01:00:18,180 ამ მხოლოდ ინიციალიზაცია მთელი მასივი იყოს 0S. 738 01:00:18,180 --> 01:00:25,320 ასე რომ, თუ არ გსურთ, რომ, მაშინ შემეძლო ცალკე გააკეთოს (int i = 0; 739 01:00:25,320 --> 01:00:31,500 I 01:00:35,260 ასე რომ ახლა ყველაფერი ინიციალიზაცია რომ 0. 741 01:00:35,260 --> 01:00:39,570 მე iterate მეტი ჩემი მასივი, 742 01:00:39,570 --> 01:00:51,920 და რა ვარ აკეთებს არის მე დათვლის რიგი ყოველ - მოდი ქვემოთ აქ. 743 01:00:51,920 --> 01:00:55,480 ჩვენ გვყავს 4, 15, 16, 50, 8, 23, 42, 108. 744 01:00:55,480 --> 01:01:00,010 რა მე დათვლის პროცესი ხმების დამთხვევა თითოეული იმ ელემენტებს. 745 01:01:00,010 --> 01:01:03,470 მოდით რეალურად დაამატოთ წყვილი მეტი აქ ზოგიერთი მეორდება. 746 01:01:03,470 --> 01:01:11,070 ამიტომ ღირებულება გვაქვს აქ, ღირებულება, რომელიც იქნება array [i]. 747 01:01:11,070 --> 01:01:14,850 ამიტომ Val შეიძლება იყოს 4 ან 8 ან რასაც. 748 01:01:14,850 --> 01:01:18,870 და ახლა მე დათვლის რამდენი, რომ ღირებულება მე ვნახე, 749 01:01:18,870 --> 01:01:21,230 ასე ითვლის [Val] + +; 750 01:01:21,230 --> 01:01:29,430 ამის შემდეგ კეთდება, ითვლის აპირებს გამოიყურებოდეს მსგავსი რამ 0001. 751 01:01:29,430 --> 01:01:42,190 მოდით ითვლის [Val] - ვალდებული + 1. 752 01:01:42,190 --> 01:01:48,230 >> ახლა ეს მხოლოდ გათვალისწინებით იმისა, რომ ჩვენ დაწყებული 0. 753 01:01:48,230 --> 01:01:50,850 ასე რომ, თუ 200 იქნება ჩვენი ყველაზე დიდი რაოდენობის, 754 01:01:50,850 --> 01:01:54,720 მაშინ 0 დან 200 არის 201 რამ. 755 01:01:54,720 --> 01:02:01,540 ასე რომ ითვლის, იგი ყველაფერს ჰგავს 00001, რადგან ჩვენ გვაქვს ერთი 4. 756 01:02:01,540 --> 01:02:10,210 მაშინ გვექნება 0001, სადაც ჩვენ გვექნება 1 მე -8 მაჩვენებელი რაოდენობა. 757 01:02:10,210 --> 01:02:14,560 ჩვენ გვექნება 2 წელს 23 მაჩვენებელი რაოდენობა. 758 01:02:14,560 --> 01:02:17,630 ჩვენ გვექნება 2 წელს 42 მაჩვენებელი რაოდენობა. 759 01:02:17,630 --> 01:02:21,670 ასე რომ ჩვენ შეგვიძლია გამოვიყენოთ რაოდენობა. 760 01:02:34,270 --> 01:02:44,920 ამიტომ num_of_item = ითვლის [i]. 761 01:02:44,920 --> 01:02:52,540 და ასე თუ num_of_item არის 2, ეს ნიშნავს, რომ ჩვენ გვინდა ჩადეთ 2 რაოდენობის I 762 01:02:52,540 --> 01:02:55,290 ჩვენს დახარისხებული მასივი. 763 01:02:55,290 --> 01:03:02,000 ამიტომ, ჩვენ უნდა ტრეკზე, თუ რამდენად შორს ვართ შევიდა მასივი. 764 01:03:02,000 --> 01:03:05,470 ასე ინდექსი = 0. 765 01:03:05,470 --> 01:03:09,910 Array - მე უბრალოდ დაწერა. 766 01:03:16,660 --> 01:03:18,020 ითვლის - 767 01:03:19,990 --> 01:03:28,580 array [ინდექსი + +] = i; 768 01:03:28,580 --> 01:03:32,490 ის არის, რომ რაც მე მინდა? მე ვფიქრობ, რომ ის, რაც მე მინდა. 769 01:03:35,100 --> 01:03:38,290 დიახ, ეს გამოიყურება კარგი. Okay. 770 01:03:38,290 --> 01:03:43,050 ამიტომ ამჯამად ყველას გვესმოდეს რა მიზნით ჩემი ითვლის მასივი? 771 01:03:43,050 --> 01:03:48,140 იგი დათვლის რიგი შემთხვევები თითოეული ამ ნომრებზე. 772 01:03:48,140 --> 01:03:51,780 მაშინ მე iterating მეტი რომ ითვლის მასივი, 773 01:03:51,780 --> 01:03:57,190 და შ პოზიცია ითვლის მასივი 774 01:03:57,190 --> 01:04:01,930 არის რიგი მე რომ უნდა გამოჩნდება ჩემი დახარისხებული მასივი. 775 01:04:01,930 --> 01:04:06,840 ამიტომ ითვლის 4 იქნება 1 776 01:04:06,840 --> 01:04:11,840 და ითვლის 8 დან იქნება 1, ითვლის 23 იქნება 2. 777 01:04:11,840 --> 01:04:16,900 ასე რომ, თუ რამდენი მათგანი მინდა INSERT INTO ჩემი დახარისხებული მასივი. 778 01:04:16,900 --> 01:04:19,200 მაშინ მე უბრალოდ რომ. 779 01:04:19,200 --> 01:04:28,960 მე ჩასმა num_of_item მე არის ჩემს დახარისხებული მასივი. 780 01:04:28,960 --> 01:04:31,670 >> კითხვები? 781 01:04:32,460 --> 01:04:43,100 და ა.შ. ერთხელ, ეს არის წრფივი, რადგან ჩვენ უბრალოდ iterating ამ ერთხელ, 782 01:04:43,100 --> 01:04:47,470 მაგრამ ასევე ხაზოვანი რა ეს ნომერი ხდება იყოს, 783 01:04:47,470 --> 01:04:50,730 ამიტომ მძიმედ დამოკიდებული, თუ რა თქვენი ბლოკნოტის არის. 784 01:04:50,730 --> 01:04:53,290 ერთად შეკრული, 200, რომ არ არის, რომ ცუდი. 785 01:04:53,290 --> 01:04:58,330 თუ თქვენი შეკრული იქნება 10,000, მაშინ რომ ცოტა უარესი, 786 01:04:58,330 --> 01:05:01,360 მაგრამ თუ თქვენი შეკრული იქნება 4 მილიარდი, რომ სრულიად არარეალური 787 01:05:01,360 --> 01:05:07,720 და ამ მასივი აპირებს უნდა იყოს ზომა 4 მილიარდი, რომელიც არარეალურია. 788 01:05:07,720 --> 01:05:10,860 ასე რომ, რომ. კითხვები? 789 01:05:10,860 --> 01:05:13,270 [Inaudible სტუდენტი საპასუხოდ] >> Okay. 790 01:05:13,270 --> 01:05:15,710 მე მივხვდი ერთ სხვა რამ, როდესაც ჩვენ გადის. 791 01:05:17,980 --> 01:05:23,720 ვფიქრობ პრობლემა იყო ლუკას და ალბათ თითოეული ჩვენ ვნახეთ. 792 01:05:23,720 --> 01:05:26,330 მე სრულიად დაავიწყდა. 793 01:05:26,330 --> 01:05:31,040 ერთადერთი, რაც მინდოდა კომენტარის გაკეთება, რომ როდესაც თქვენ საქმე რამ, როგორიცაა ინდექსები, 794 01:05:31,040 --> 01:05:38,320 თქვენ არასდროს ვხედავ ამ როდესაც თქვენ წერა ამისთვის მარყუჟის, 795 01:05:38,320 --> 01:05:41,120 მაგრამ ტექნიკურად, როდესაც თქვენ საქმე ამ მაჩვენებლების, 796 01:05:41,120 --> 01:05:45,950 თქვენ უნდა საკმაოდ ბევრი ყოველთვის გაუმკლავდეთ ხელმოუწერელი რიცხვებით. 797 01:05:45,950 --> 01:05:53,850 მიზეზი არის ის, როდესაც თქვენ საქმე ხელმოწერილი რიცხვებით, 798 01:05:53,850 --> 01:05:56,090 ასე რომ, თუ თქვენ გაქვთ 2 ხელმოწერილი რიცხვებით და დაამატოთ ისინი ერთად 799 01:05:56,090 --> 01:06:00,640 და მათ დასრულდება მდე ძალიან დიდი, მაშინ დასრულდება up ერთად უარყოფითი რიცხვი. 800 01:06:00,640 --> 01:06:03,410 ასე რომ სწორედ ეს რიცხვი overflow არის. 801 01:06:03,410 --> 01:06:10,500 >> თუ დავამატო 2 მილიარდი და 1 მილიარდი, მე დასრულდება მდე ნეგატიური 1 მილიარდი. 802 01:06:10,500 --> 01:06:15,480 ასე რიცხვებით მუშაობა კომპიუტერი. 803 01:06:15,480 --> 01:06:17,510 ასე რომ პრობლემა გამოყენებით - 804 01:06:17,510 --> 01:06:23,500 სწორედ ჯარიმის გარდა, თუ დაბალი მოხდება იქნება 2 მილიარდი და ხდება იყოს 1 მილიარდი, 805 01:06:23,500 --> 01:06:27,120 მაშინ ეს იქნება უარყოფითი 1 მილიარდი და შემდეგ ჩვენ ვაპირებთ გაყოფა, რომ 2 806 01:06:27,120 --> 01:06:29,730 და დასრულდება მდე უარყოფითი 500 მილიონი. 807 01:06:29,730 --> 01:06:33,760 ასე რომ, ეს მხოლოდ საკითხის თუ მოხდება უნდა ეძებს მეშვეობით მასივი 808 01:06:33,760 --> 01:06:38,070 მილიარდობით რამ. 809 01:06:38,070 --> 01:06:44,050 მაგრამ თუ დაბალი + up ხდება overflow, მაშინ რომ პრობლემა. 810 01:06:44,050 --> 01:06:47,750 როგორც კი ჩვენ მათ ხელმოუწერელი, მაშინ 2 მილიარდი პლუს 1 მილიარდი არის 3 მილიარდი. 811 01:06:47,750 --> 01:06:51,960 3 მილიარდი იყოფა 2 არის 1,5 მილიარდი. 812 01:06:51,960 --> 01:06:55,670 ამიტომ, როგორც კი ისინი ხელმოუწერელი, ყველაფერი სრულყოფილი. 813 01:06:55,670 --> 01:06:59,900 და ისე, რომ ასევე საკითხი, როდესაც თქვენ წერილობით თქვენი ამისთვის მარყუჟების, 814 01:06:59,900 --> 01:07:03,940 და ფაქტობრივად, ეს ალბათ აკეთებს ავტომატურად. 815 01:07:09,130 --> 01:07:12,330 ეს იქნება რეალურად მხოლოდ დაწეროთ თქვენ. 816 01:07:12,330 --> 01:07:21,610 ასე რომ, თუ ეს რიცხვი ძალიან დიდია, რომ მხოლოდ მთელი რიცხვი, მაგრამ ეს არ შეესაბამება ხელმოუწერელი რიცხვი, 817 01:07:21,610 --> 01:07:24,970 ეს იქნება დაწეროთ თქვენ, ასე ამიტომაც არასოდეს ნამდვილად გადაეყარონ საკითხი. 818 01:07:29,150 --> 01:07:34,820 თქვენ ხედავთ, რომ ინდექსის არასდროს იქნება უარყოფითი, 819 01:07:34,820 --> 01:07:39,220 და ამრიგად, როდესაც თქვენ iterating მეტი მასივი, 820 01:07:39,220 --> 01:07:43,970 შეგიძლიათ თითქმის ყოველთვის ვამბობ ხელმოუწერელი int i, მაგრამ თქვენ ნამდვილად არ უნდა. 821 01:07:43,970 --> 01:07:47,110 ყველაფერი იმუშავებს საკმაოდ ბევრი უბრალოდ ისევე. 822 01:07:48,740 --> 01:07:50,090 Okay. [ჩურჩული] რომელი საათია? 823 01:07:50,090 --> 01:07:54,020 ბოლო რამ მინდოდა, - და მე უბრალოდ მართლაც სწრაფი. 824 01:07:54,020 --> 01:08:03,190 თქვენ იცით, თუ როგორ ჩვენ # განსაზღვრავს ასე შეგვიძლია # define MAX როგორც 5 ან რაღაც? 825 01:08:03,190 --> 01:08:05,940 მოდით არ გააკეთებს MAX. # განსაზღვრავს დავალდებულებულნი 200. რაც გავაკეთეთ ადრე. 826 01:08:05,940 --> 01:08:10,380 რომელიც განსაზღვრავს მუდმივი, რომელიც მხოლოდ უნდა გადაწერა და pasted 827 01:08:10,380 --> 01:08:13,010 იქ, სადაც ჩვენ მოხდეს დაწერა იკვრება. 828 01:08:13,010 --> 01:08:18,189 >> ასე რომ ჩვენ შეგვიძლია რეალურად უფრო მეტი ერთად # განსაზღვრავს. 829 01:08:18,189 --> 01:08:21,170 ჩვენ შეგვიძლია # განსაზღვრავს ფუნქციებს. 830 01:08:21,170 --> 01:08:23,410 ისინი ნამდვილად არ ფუნქციებს, მაგრამ ჩვენ მოვუწოდებთ მათ ფუნქციებს. 831 01:08:23,410 --> 01:08:36,000 მაგალითი იქნება რაღაც MAX (x, y) განისაზღვრება როგორც (x 01:08:40,660 ასე, რომ თქვენ უნდა შეეგუოს ternary ოპერატორის სინტაქსი, 833 01:08:40,660 --> 01:08:49,029 მაგრამ არის x ნაკლები Y? დაბრუნება Y, სხვაგან დაბრუნების x. 834 01:08:49,029 --> 01:08:54,390 ასე რომ თქვენ ხედავთ, შეგიძლიათ ამ ფუნქციის ცალკე, 835 01:08:54,390 --> 01:09:01,399 და ფუნქცია შეიძლება იყოს bool MAX იღებს 2 არგუმენტები, დააბრუნოს ეს. 836 01:09:01,399 --> 01:09:08,340 ეს არის ერთ ერთი ყველაზე საერთო პირობა ვხედავ გაკეთდეს მოსწონს ეს. ჩვენ მოვუწოდებთ მათ macros. 837 01:09:08,340 --> 01:09:11,790 ეს არის მაკრო. 838 01:09:11,790 --> 01:09:15,859 ეს არის მხოლოდ სინტაქსი იგი. 839 01:09:15,859 --> 01:09:18,740 თქვენ შეგიძლიათ დაწეროთ მაკრო გავაკეთოთ რაც გაგიხარდებათ. 840 01:09:18,740 --> 01:09:22,649 თქვენ ხშირად ვხედავ macros for გამართვის printfs და პერსონალი. 841 01:09:22,649 --> 01:09:29,410 ასე ტიპის printf, არსებობს სპეციალური მუდმივებზე C მოსწონს ხაზგასმა LINE ხაზგასასმელად, 842 01:09:29,410 --> 01:09:31,710 2 ხაზს უსვამს ხაზს ხაზი, 843 01:09:31,710 --> 01:09:37,550 და არის კიდევ ვფიქრობ 2 ხაზს FUNC. ეს შეიძლება იგი. რამე მაგდაგვარს. 844 01:09:37,550 --> 01:09:40,880 იმ რამ შეიცვლება სახელით ფუნქცია 845 01:09:40,880 --> 01:09:42,930 ან ხმების ხაზი, რომ თქვენ შესახებ. 846 01:09:42,930 --> 01:09:48,630 ხშირად წერთ გამართვის printfs რომ ქვევით აქ შემეძლო მაშინ უბრალოდ დაწერეთ 847 01:09:48,630 --> 01:09:54,260 Debug და იქნება ბეჭდვა ხაზის ნომერი და ფუნქცია, რომ მე არ უნდა იყოს 848 01:09:54,260 --> 01:09:57,020 რომ იგი შეექმნა, რომ გამართვის განცხადებაში. 849 01:09:57,020 --> 01:09:59,550 და ასევე შეგიძლიათ ბეჭდვა სხვა რამ. 850 01:09:59,550 --> 01:10:05,990 ასე რომ ერთი რამ უნდა ფრთხილად არის თუ ემართება # განსაზღვრავს DOUBLE_MAX 851 01:10:05,990 --> 01:10:11,380 როგორც რაღაც 2 * Y-სა და 2 * x. 852 01:10:11,380 --> 01:10:14,310 ამიტომ სხვადსხვა მიზეზის გამო, თქვენ არ უნდა გავაკეთოთ, რომ ბევრი. 853 01:10:14,310 --> 01:10:16,650 ასე რომ ეს მაკრო. 854 01:10:16,650 --> 01:10:18,680 ეს არის რეალურად გატეხილი. 855 01:10:18,680 --> 01:10:23,050 მინდა მოვუწოდო მას ამით რაღაც DOUBLE_MAX (3, 6). 856 01:10:23,050 --> 01:10:27,530 მერე რა უნდა დაუბრუნდეს? 857 01:10:28,840 --> 01:10:30,580 [სტუდენტი] 12. 858 01:10:30,580 --> 01:10:34,800 დიახ, 12 უნდა დაუბრუნდეს და 12 ბრუნდება. 859 01:10:34,800 --> 01:10:43,350 3 იღებს შეცვალა ამისთვის x, 6 იღებს შეცვალა ამისთვის Y, და ვბრუნდებით 2 * 6, რაც 12. 860 01:10:43,350 --> 01:10:47,710 ახლა რაც შეეხება ამ საკითხთან დაკავშირებით? რა უნდა დაბრუნდნენ? 861 01:10:47,710 --> 01:10:50,330 [სტუდენტი] 14. >> იდეალურ შემთხვევაში, 14. 862 01:10:50,330 --> 01:10:55,290 საკითხი არის ის, რომ როგორ hash განსაზღვრავს სამუშაოს, გახსოვდეთ ეს ლიტერატურული ასლი და პასტა 863 01:10:55,290 --> 01:11:00,160 საქართველოს საკმაოდ ბევრი ყველაფერი, ასე რომ ეს იქნება გაგებული, როგორც 864 01:11:00,160 --> 01:11:11,270 არის 3 ზე ნაკლები 1 plus 6, 2 ჯერ 1 plus 6, 2 ჯერ 3. 865 01:11:11,270 --> 01:11:19,780 >> ასე რომ, ამ მიზეზით თითქმის ყოველთვის გადაიტანოთ ყველაფერი ფრჩხილებში. 866 01:11:22,180 --> 01:11:25,050 ნებისმიერი ცვლადი თქვენ თითქმის ყოველთვის გადაიტანოთ ფრჩხილებში. 867 01:11:25,050 --> 01:11:29,570 არის შემთხვევები, სადაც თქვენ არ უნდა, ისევე როგორც მე ვიცი, რომ მე არ უნდა გავაკეთოთ, რომ აქ 868 01:11:29,570 --> 01:11:32,110 რადგან ნაკლები არის საკმაოდ ბევრი ყოველთვის მხოლოდ იმუშავებს, 869 01:11:32,110 --> 01:11:34,330 თუმცა, რომ შეიძლება არც კი იყოს ჭეშმარიტი. 870 01:11:34,330 --> 01:11:41,870 რამე სასაცილოა, როგორიც DOUBLE_MAX (1 == 2), 871 01:11:41,870 --> 01:11:49,760 მაშინ ეს ხდება მისაღებად შეცვალა 3 ზე ნაკლები 1 უდრის უდრის 2, 872 01:11:49,760 --> 01:11:53,460 და ასე შემდეგ ის აპირებს 3 ზე ნაკლები 1, ამჯამად რომ თანაბარი 2, 873 01:11:53,460 --> 01:11:55,620 რომელიც არ არის ის რაც ჩვენ გვინდა. 874 01:11:55,620 --> 01:12:00,730 ამიტომ, რათა ნებისმიერი ოპერატორის პრეცენდენტის პრობლემები, 875 01:12:00,730 --> 01:12:02,870 ყოველთვის გადაიტანოთ ფრჩხილებში. 876 01:12:03,290 --> 01:12:07,700 Okay. და ამით ყველაფერი, 5:30. 877 01:12:08,140 --> 01:12:12,470 თუ თქვენ გაქვთ რაიმე შეკითხვა pset, გვაცნობოთ. 878 01:12:12,470 --> 01:12:18,010 ეს უნდა იყოს სახალისო და ჰაკერული გამოცემა ასევე ბევრად უფრო რეალურია 879 01:12:18,010 --> 01:12:22,980 ვიდრე Hacker გამოცემა გასულ წელს, ასე რომ იმედი გვაქვს, რომ ბევრი თქვენგანი ცდილობენ. 880 01:12:22,980 --> 01:12:26,460 გასულ წელს იყო ძალიან დიდი. 881 01:12:28,370 --> 01:12:30,000 >> [CS50.TV]