1
00:00:00,000 --> 00:00:05,726
>> [সঙ্গীত বাজাচ্ছি]

2
00:00:05,726 --> 00:00:08,600
ডগ লয়েড: নির্বাচন সাজানোর একটি হল
আপনি আশা করতে পারে, যে অ্যালগরিদম,

3
00:00:08,600 --> 00:00:10,470
উপাদানের একটি সেট অসুস্থ.

4
00:00:10,470 --> 00:00:12,470
এবং এলগরিদম রিকল
একটি ধাপে ধাপে সেট

5
00:00:12,470 --> 00:00:15,260
একটি কাজ শেষ করার জন্য নির্দেশনা দেওয়া.

6
00:00:15,260 --> 00:00:17,580
>> নির্বাচন সাজানোর
মৌলিক ধারণা, এই হল

7
00:00:17,580 --> 00:00:22,080
ক্ষুদ্রতম পাঁচমিশালী উপাদান খুঁজে পেতে এবং
সাজানো তালিকার শেষে এটি যোগ করুন.

8
00:00:22,080 --> 00:00:26,970
কার্যকরভাবে এই কি বিল্ড
একটি সাজানো তালিকা, একটি সময়ে এক উপাদান.

9
00:00:26,970 --> 00:00:29,800
Pseudocode হয় তা নিচে ব্রেকিং
আমরা এই অ্যালগরিদম রাজ্য পারে

10
00:00:29,800 --> 00:00:34,490
নিম্নরূপ, যতক্ষণ এই পুনরাবৃত্তি
কোন পাঁচমিশালী উপাদান থাকা.

11
00:00:34,490 --> 00:00:38,660
পাঁচমিশালী মাধ্যমে অনুসন্ধান
তথ্য ক্ষুদ্রতম মান খুঁজে,

12
00:00:38,660 --> 00:00:44,130
তারপর সঙ্গে ক্ষুদ্রতম মান অদলবদল
পাঁচমিশালী অংশ প্রথম উপাদান.

13
00:00:44,130 --> 00:00:47,130
>> এটা, এই দৃশ্য কল্পনা করতে সাহায্য করতে পারে
তাই আসুন এই কটাক্ষপাত করা যাক.

14
00:00:47,130 --> 00:00:49,710
তাই এই, আমি তর্কবিতর্ক, একটি হল
পাঁচমিশালী অ্যারে এবং আমি করেছি

15
00:00:49,710 --> 00:00:53,040
সব যা নির্দেশ করে এটি নির্দেশিত
উপাদানের, রঙ্গিন লাল

16
00:00:53,040 --> 00:00:54,420
তারা এখনো সাজানো না হয়.

17
00:00:54,420 --> 00:00:57,670
এই সমগ্র হয়
অ্যারের পাঁচমিশালী অংশ.

18
00:00:57,670 --> 00:01:02,020
>> সুতরাং আসুন পদক্ষেপের মধ্য দিয়ে যেতে দেওয়া
নির্বাচন সাজানোর এই অ্যারের সাজাতে.

19
00:01:02,020 --> 00:01:05,296
তাই আবার, আমরা এটাকে পুনরাবৃত্ত আছেন
কোন পাঁচমিশালী উপাদান থাকা পর্যন্ত.

20
00:01:05,296 --> 00:01:07,920
আমরা মাধ্যমে কাজ করত অনুসন্ধান আছেন
তথ্য ক্ষুদ্রতম মান খুঁজে,

21
00:01:07,920 --> 00:01:11,990
এবং তারপর সাথে যে মান অদলবদল
পাঁচমিশালী অংশ প্রথম উপাদান.

22
00:01:11,990 --> 00:01:14,380
>> ঠিক এখন, আবার সমগ্র
অ্যারে পাঁচমিশালী অংশ.

23
00:01:14,380 --> 00:01:16,534
লাল উপাদানের সমস্ত পাঁচমিশালী হয়.

24
00:01:16,534 --> 00:01:18,700
সুতরাং আমরা মাধ্যমে অনুসন্ধান ও
আমরা ক্ষুদ্রতম মান এটি.

25
00:01:18,700 --> 00:01:20,533
আমরা শুরুতে শুরু
আমরা, শেষে যান

26
00:01:20,533 --> 00:01:23,630
আমরা ক্ষুদ্রতম মান, এক এটি.

27
00:01:23,630 --> 00:01:24,860
সুতরাং যে অংশ এক.

28
00:01:24,860 --> 00:01:29,440
এবং তারপর অংশ দুটি, সঙ্গে যে মান অদলবদল
পাঁচমিশালী অংশ প্রথম উপাদান,

29
00:01:29,440 --> 00:01:31,340
অথবা প্রথম লাল উপাদান.

30
00:01:31,340 --> 00:01:34,980
>> এই ক্ষেত্রে হতে হবে
পাঁচ, তাই আমরা এক ও পাঁচটি অদলবদল.

31
00:01:34,980 --> 00:01:37,320
আমরা এই কাজ করি, তখন আমরা যা করতে পারেন
দৃশ্যত আমরা করেছি দেখতে

32
00:01:37,320 --> 00:01:41,260
ক্ষুদ্রতম মূল্যবান উপাদান স্থানান্তরিত
অ্যারের, খুব শুরুতে.

33
00:01:41,260 --> 00:01:43,920
কার্যকরভাবে যে উপাদান বাছাই.

34
00:01:43,920 --> 00:01:47,520
>> আর তাই আমরা অবশ্যই নিশ্চিত করতে পারেন
এবং রাষ্ট্র এক, যে সাজানো হয়.

35
00:01:47,520 --> 00:01:52,080
আর তাই আমরা অনুসারে বাছাই করা অংশ ইঙ্গিত করব
আমাদের অ্যারের, এটা নীল রং করে.

36
00:01:52,080 --> 00:01:53,860
>> এখন আমরা আবার প্রক্রিয়ার পুনরাবৃত্তি.

37
00:01:53,860 --> 00:01:57,430
আমরা পাঁচমিশালী অংশ মাধ্যমে অনুসন্ধান
অ্যারে ক্ষুদ্রতম উপাদান খুঁজে পেতে.

38
00:01:57,430 --> 00:01:59,000
এই ক্ষেত্রে, এটা দুই এর.

39
00:01:59,000 --> 00:02:02,100
>> আমরা প্রথম যে অদলবদল
পাঁচমিশালী অংশ উপাদান.

40
00:02:02,100 --> 00:02:05,540
এই ক্ষেত্রে দুটি উদাহরণ হতে হবে
পাঁচমিশালী অংশ প্রথম উপাদান.

41
00:02:05,540 --> 00:02:08,650
সুতরাং আমরা নিজেই সঙ্গে দুই অদলবদল,
যা সত্যিই, মাত্র দুটি ছেড়ে

42
00:02:08,650 --> 00:02:11,257
এটা হয়, এবং এটি সাজানো যেখানে.

43
00:02:11,257 --> 00:02:13,840
উপর অব্যাহত, আমরা মাধ্যমে অনুসন্ধান
ক্ষুদ্রতম উপাদান খুঁজে পেতে.

44
00:02:13,840 --> 00:02:15,030
এটি তিন.

45
00:02:15,030 --> 00:02:17,650
আমরা প্রথম সাথে বিনিময়
পাঁচটি যা উপাদান.

46
00:02:17,650 --> 00:02:19,450
এবং এখন তিনটি সাজানো হয়.

47
00:02:19,450 --> 00:02:22,440
>> আমরা আবার মাধ্যমে অনুসন্ধান, এবং আমরা
ক্ষুদ্রতম উপাদান চারটি হল এটি.

48
00:02:22,440 --> 00:02:28,070
আমরা প্রথম উপাদান সাথে বিনিময়
পাঁচমিশালী অংশ, এবং এখন চার সাজানো হয়.

49
00:02:28,070 --> 00:02:29,910
>> আমরা পাঁচটি যে এটি
ক্ষুদ্রতম উপাদান.

50
00:02:29,910 --> 00:02:32,900
আমরা প্রথম সাথে বিনিময়
পাঁচমিশালী অংশ উপাদান.

51
00:02:32,900 --> 00:02:34,740
আর এখন পাঁচটি সাজানো হয়.

52
00:02:34,740 --> 00:02:36,660
>> এবং তারপর সর্বশেষে, আমাদের
পাঁচমিশালী অংশ গঠিত

53
00:02:36,660 --> 00:02:38,576
শুধু একটি একক উপাদান,
তাই আমরা মাধ্যমে অনুসন্ধান

54
00:02:38,576 --> 00:02:41,740
এবং আমরা ছয় যে এটি
ক্ষুদ্রতম, এবং আসলে, একমাত্র উপাদান.

55
00:02:41,740 --> 00:02:44,906
এবং তারপর আমরা এটা সাজানো হয় যে রাষ্ট্র পারে.

56
00:02:44,906 --> 00:02:47,530
আর এখন আমরা আমাদের অ্যারের সুইচ করেছি
সম্পূর্ণ পাঁচমিশালী হচ্ছে থেকে

57
00:02:47,530 --> 00:02:52,660
লাল, সম্পূর্ণ সাজানো করতে
নীল, নির্বাচন সাজানোর ব্যবহার.

58
00:02:52,660 --> 00:02:54,920
>> সুতরাং এ লক দৃশ্যকল্প এখানে কি?

59
00:02:54,920 --> 00:02:57,830
পাশাপাশি পরম খারাপ
যদি আমরা ধরে পর্যবেক্ষণ আছে

60
00:02:57,830 --> 00:03:02,170
অ্যারে উপাদান সব
ক্ষুদ্রতম পাঁচমিশালী উপাদান খুঁজে,

61
00:03:02,170 --> 00:03:04,750
এবং আমরা পুনরাবৃত্তি আছে
এই প্রক্রিয়া এন বার.

62
00:03:04,750 --> 00:03:09,090
অ্যারের প্রতিটি উপাদান জন্য একবার
আমরা শুধুমাত্র কারণ, এই অ্যালগরিদম,

63
00:03:09,090 --> 00:03:12,180
সময়ে সাজান এক উপাদান.

64
00:03:12,180 --> 00:03:13,595
>> শ্রেষ্ঠ কেস দৃশ্যকল্প কী?

65
00:03:13,595 --> 00:03:15,040
আচ্ছা এটা ঠিক আছে, ঠিক একই?

66
00:03:15,040 --> 00:03:18,440
আমরা আসলে এখনো মাধ্যমে সিঁড়ির ধাপ আছে
অ্যারের প্রতিটি উপাদান

67
00:03:18,440 --> 00:03:22,040
যাতে এটি হয় তা নিশ্চিত করতে
আসলে, ক্ষুদ্রতম উপাদান.

68
00:03:22,040 --> 00:03:26,760
>> তাই সবচেয়ে খারাপ ক্ষেত্রে রানটাইম, আমরা
একটি প্রক্রিয়া এন বার পুনরাবৃত্তি আছে,

69
00:03:26,760 --> 00:03:28,960
এন উপাদানের জন্য প্রতিটি একবার.

70
00:03:28,960 --> 00:03:31,940
এবং শ্রেষ্ঠ কেস দৃশ্যকল্প,
আমরা একই কাজ করতে হবে.

71
00:03:31,940 --> 00:03:35,340
>> তাই ফিরে চিন্তা আমাদের
গণনীয় জটিলতা টুলবক্স,

72
00:03:35,340 --> 00:03:39,250
আপনি কি মনে করেন খারাপ হয়
নির্বাচন সাজানোর জন্য ক্ষেত্রে রানটাইম?

73
00:03:39,250 --> 00:03:41,840
আপনি কি মনে করেন সেরা হয়
নির্বাচন সাজানোর জন্য ক্ষেত্রে রানটাইম?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> N ছক আপনাকে বিগ হে অনুমান করেছেন,
এবং বিগ ওমেগা n এর ছক?

76
00:03:49,325 --> 00:03:49,950
আপনি সঠিক হতে চাই.

77
00:03:49,950 --> 00:03:52,490
এরাই হলো, আসলে,
খারাপ ক্ষেত্রে ও সেরা ক্ষেত্রে চালান

78
00:03:52,490 --> 00:03:55,100
নির্বাচন সাজানোর জন্য টাইমস অব ইন্ডিয়া.

79
00:03:55,100 --> 00:03:56,260
>> আমি ডগ লয়েড আছি.

80
00:03:56,260 --> 00:03:58,600
এটি CS50.

81
00:03:58,600 --> 00:04:00,279