1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [সাজান মার্জ]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - হার্ভার্ড বিশ্ববিদ্যালয়]

3
00:00:04,000 --> 00:00:07,000
[এটি CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
এর একত্রীকরণ সাজানোর সম্পর্কে কথা বলা যাক.

5
00:00:09,000 --> 00:00:14,000
এ পর্যন্ত আপনি বুদ্বুদ সাজানোর, সন্নিবেশ সাজানোর, এবং নির্বাচন সাজানোর দেখা করেছি.

6
00:00:14,000 --> 00:00:17,000
যদিও আমি ভাল দ্বারা মানে আমার হাত তরঙ্গ ধরনের করব,

7
00:00:17,000 --> 00:00:21,000
সাজানোর একত্রীকরণ সাধারণত সঞ্চালিত এই 3 প্রকারের কোনো চেয়ে ভাল.

8
00:00:22,000 --> 00:00:27,000
>> কিন্তু একত্রীকরণ সাজানোর বিষয়ে কথা আগে, আসুন 2 অনুসারে সাজানো তালিকা মার্জ সম্পর্কে কথা বলুন.

9
00:00:27,000 --> 00:00:31,000
আমরা এই মত অনুসারে সাজানো তালিকা 2 গ্রহণের প্রক্রিয়া কল, করব,

10
00:00:31,000 --> 00:00:35,000
এবং একটি একক তাদের অনুসারে সাজানো তালিকা তৈরীর আউট - সুচী মার্জ.

11
00:00:35,000 --> 00:00:37,750
কিভাবে এই আমরা কি করতে পারি?

12
00:00:37,750 --> 00:00:41,290
তবে, ধারণা শুধু অন্যান্য তালিকার শেষে সম্মুখের একটি তালিকা বিদ্ধ করা হয়

13
00:00:41,290 --> 00:00:43,830
এবং তারপর অনুসন্ধানের ফলাফলের তালিকায় সাজাতে.

14
00:00:43,830 --> 00:00:47,220
>> যদিও এই কাজ করে, এটা অপ্রয়োজনীয় কাজ অনেক.

15
00:00:47,220 --> 00:00:49,900
আমরা শুধু বাছাই চেয়ে এটা দ্রুত করতে পারেন.

16
00:00:49,900 --> 00:00:54,100
উল্লেখ্য, একটি ভুল ধারণা মাত্র প্রতিটি তালিকা থেকে পর্যায়ক্রমে কাপ নিতে হয়.

17
00:00:54,100 --> 00:00:56,460
যদিও যে যে কাজ মত প্রথমে মনে হতে পারে,

18
00:00:56,460 --> 00:01:05,760
করছেন যা আমরা 4, 8, 15, 23, 16 সঙ্গে শেষ - বিজ্ঞপ্তি অনুযায়ী 16 এবং 23 জায়গা হয়ে গেছে.

19
00:01:05,760 --> 00:01:09,380
কারণ 2 উপাদান আছে যা মার্জ তালিকা প্রদর্শিত পরপর করা উচিত

20
00:01:09,380 --> 00:01:11,720
একই প্রারম্ভিক তালিকা আছে.

21
00:01:11,720 --> 00:01:14,850
উভয় 15 এবং 16 বাম দিকের তালিকার মধ্যে.

22
00:01:14,850 --> 00:01:19,810
কৌতুক যাও যে ইতিমধ্যে উভয় তালিকা অনুসারে বাছাই করা হয় সদ্ব্যবহার করা হয়.

23
00:01:19,810 --> 00:01:23,320
এর মানে হল যে যদি আমরা শুধুমাত্র উভয় তালিকার প্রথম উপাদান তাকান -

24
00:01:23,320 --> 00:01:29,580
এখানে, 4 এবং 8 - এ তাদের একজন হতে মার্জ তালিকার প্রথম উপাদান আবশ্যক.

25
00:01:29,580 --> 00:01:31,620
ভাল, কেন হল?

26
00:01:31,620 --> 00:01:33,520
এই তালিকা দুটি ইতিমধ্যেই সাজানো,

27
00:01:33,520 --> 00:01:38,410
এবং তাই হয় 4 বা 8 ক্ষুদ্রতম উপাদান যখন আমরা 2 তালিকা একত্রিত হতে হবে.

28
00:01:38,410 --> 00:01:41,770
এই ক্ষেত্রে, ক্ষুদ্রতম 4 টি,

29
00:01:41,770 --> 00:01:46,370
তাই আমরা 4 সময় নিন এবং এটি আমাদের মার্জ তালিকার প্রথম উপাদান করতে পারেন.

30
00:01:46,370 --> 00:01:50,710
এখন আমরা অবশিষ্ট প্রথম তালিকার 3 উপাদান মার্জ অবিরত

31
00:01:50,710 --> 00:01:52,920
এবং দ্বিতীয় তালিকার 4 উপাদান.

32
00:01:52,920 --> 00:01:57,150
>> আবার, আমরা শুধুমাত্র উভয় তালিকার প্রথম উপাদান তাকান প্রয়োজন.

33
00:01:57,150 --> 00:02:01,060
2 ছোট আমাদের মার্জ তালিকার দ্বিতীয় উপাদান হতে হবে.

34
00:02:01,060 --> 00:02:05,440
8 এবং 15 এর মধ্যে এই সময়, 8 ক্ষুদ্রতম হয়, এবং তাই আমরা যে সন্নিবেশ

35
00:02:05,440 --> 00:02:09,240
হিসাবে আমাদের অনুসারে সাজানো তালিকা দ্বিতীয় উপাদান.

36
00:02:09,240 --> 00:02:12,180
আমরা উভয় তালিকার প্রথম উপাদান তুলনা অবিরত করতে পারেন

37
00:02:12,180 --> 00:02:14,420
এবং 2 ছোট সরিয়ে ফেলা হয়.

38
00:02:14,420 --> 00:02:19,460
15 এবং 23, 15 তুলনা হয় ছোট এবং যাতে এর আমাদের তৃতীয় উপাদান.

39
00:02:21,000 --> 00:02:23,910
এখন 16 তুলনা করে এবং 23, 16 হয় ছোট.

40
00:02:23,910 --> 00:02:26,820
যাতে এর চতুর্থ উপাদান.

41
00:02:26,820 --> 00:02:30,390
>> উল্লেখ্য, 2 উপাদানের একটি সারিতে একই তালিকা থেকে এসেছিলেন.

42
00:02:30,390 --> 00:02:34,400
এটি কেন মার্জ তালিকা মাত্র 2 তালিকা থেকে বিকল্প উপাদানের করতে পারেন না.

43
00:02:34,400 --> 00:02:40,020
50 এবং 23, 23 তুলনা হয় ছোট, তাই আমরা যে নির্বাচন করুন.

44
00:02:40,770 --> 00:02:44,070
50 এবং 42 এর মধ্যে, 42 হয় ছোট.

45
00:02:44,070 --> 00:02:48,290
50 এবং 108 এর মধ্যে, 50 হয় ছোট.

46
00:02:48,290 --> 00:02:52,330
এবং পরিশেষে, আমরা মাত্র 108 আছে, তাই এটা আমাদের তালিকার শেষে অবস্থিত নেভিগেশন এড়িয়ে যেতে হবে.

47
00:02:53,750 --> 00:02:56,180
উল্লেখ্য, আমরা একটি সুন্দর, সাজানো তালিকা আছে.

48
00:02:56,180 --> 00:02:59,040
প্রতিটি সময় আমরা প্রথম 2 তালিকার 2 উপাদান তুলনা

49
00:02:59,040 --> 00:03:02,730
আমরা মার্জ তালিকা পরবর্তী উপাদান নির্ধারণ করে.

50
00:03:02,730 --> 00:03:08,070
এর মানে হল যে যদি চূড়ান্ত তালিকা n সংখ্যা, যেখানে n হল এখানে রয়েছে 8,

51
00:03:08,070 --> 00:03:12,610
তারপর আমরা যথাস্থান মধ্যে যারা সংখ্যার সব পাওয়া সবচেয়ে n তুলনা এ প্রয়োজন.

52
00:03:13,230 --> 00:03:16,230
যেমন একটি অ্যালগরিদম রৈখিক সময় চালানোর জন্য বলা হয়,

53
00:03:16,230 --> 00:03:18,090
কিন্তু যে সম্পর্কে এখানে না চিন্তা.

54
00:03:18,570 --> 00:03:22,810
>> মার্জ জন্য আমাদের এলগরিদম ব্যবহার করে, আমরা একটি দ্রুত একত্রীকরণ সাজানোর আলগোরিদিম করতে পারেন.

55
00:03:22,810 --> 00:03:25,170
সুতরাং, আসুন আমাদের তালিকা রিসেট করুন.

56
00:03:35,210 --> 00:03:37,750
2 একত্রীকরণ সাজানোর প্রক্রিয়ায় বড় ধাপ আছে.

57
00:03:37,750 --> 00:03:41,500
প্রথম অবিরত, অর্ধেক কাপ মধ্যে তালিকা বিভক্ত করুন

58
00:03:41,500 --> 00:03:44,860
যতক্ষণ না আমরা শুধু তাদের মধ্যে 1 কাপ সঙ্গে তালিকার একটি গুচ্ছ আছে.

59
00:03:44,860 --> 00:03:47,350
যদি একটি তালিকা একটি বিজোড় সংখ্যা উপস্থিত রয়েছে চিন্তা

60
00:03:47,350 --> 00:03:49,880
এবং আপনি তাদের মধ্যে পুরোপুরি কেটে পরিষ্কার করতে পারবেন না.

61
00:03:49,880 --> 00:03:53,750
শুধু ইচ্ছামত বাছাই তালিকা যা অতিরিক্ত কাপ ইন অন্তর্ভুক্ত

62
00:03:53,750 --> 00:03:56,240
সুতরাং, আসুন এই তালিকা বিভক্ত.

63
00:03:58,140 --> 00:04:01,310
এখন আমরা 2 তালিকা আছে.

64
00:04:04,120 --> 00:04:06,570
এখন আমরা 4 তালিকা আছে.

65
00:04:10,350 --> 00:04:13,870
>> এবং এখন আমরা একটি তালিকা প্রতিটি একক কাপ সঙ্গে 8 তালিকা আছে.

66
00:04:13,870 --> 00:04:16,630
যাতে এর ধাপ 1 জন্য এটি.

67
00:04:16,630 --> 00:04:22,230
ধাপ 2 জন্য, বার বার আমরা একত্রীকরণ এলগরিদম ব্যবহার করে আমরা আগে শিখেছি তালিকা জোড়া একত্রীকরণ.

68
00:04:22,230 --> 00:04:29,160
108 এবং 15 মার্জ, আমরা তালিকায় 15, 108 দিয়ে শেষ পর্যন্ত.

69
00:04:30,330 --> 00:04:36,250
50 এবং 4 মার্জ, আমরা 4, 50 দিয়ে শেষ পর্যন্ত.

70
00:04:36,960 --> 00:04:41,400
8 এবং 42 মার্জ, আমরা 8 সঙ্গে শেষ 42,.

71
00:04:42,790 --> 00:04:48,130
এবং 23 এবং 16 মার্জ, আমরা 16 সঙ্গে শেষ 23,.

72
00:04:49,740 --> 00:04:52,450
এখন সব আমাদের তালিকা আকার 2 হয়.

73
00:04:53,020 --> 00:04:56,180
উল্লেখ্য, 4 তালিকার প্রতিটি সাজানো হয়.

74
00:04:56,180 --> 00:04:59,160
>> সুতরাং আমরা তালিকা জোড়া মার্জ আবার শুরু করতে পারেন.

75
00:04:59,160 --> 00:05:03,240
15 এবং 108 এবং 4 এবং 50 মার্জ -

76
00:05:03,240 --> 00:05:11,170
প্রথম 4 টি, তাহলে 15, তারপর 50, তারপর 108.

77
00:05:11,170 --> 00:05:15,120
8, 42 এবং 16, 23 মার্জ,

78
00:05:15,120 --> 00:05:22,440
আমরা প্রথম তারপর 8, 16, তারপর 23, তারপর 42 নিতে.

79
00:05:22,440 --> 00:05:27,370
তাই এখন আমরা 4 আকার মাত্র 2 তালিকা আছে, প্রতিটি যা সাজানো হয়.

80
00:05:27,370 --> 00:05:30,980
তাই এখন আমরা এইসব 2 তালিকা একত্রীকরণ.

81
00:05:30,980 --> 00:05:33,440
প্রথম আমরা 4 নিতে.

82
00:05:33,440 --> 00:05:36,580
তারপর আমরা 8 নিতে.

83
00:05:36,580 --> 00:05:50,700
তারপর আমরা 15 এবং তারপর 16, 23, তারপর 42, তারপর 50, 108 তারপর নিতে.

84
00:05:50,700 --> 00:05:52,220
এবং আমরা কাজ সম্পন্ন হয়.

85
00:05:52,220 --> 00:05:54,900
আমরা এখন একটি অনুসারে সাজানো তালিকা আছে.

86
00:05:54,900 --> 00:05:57,890
সুতরাং কিভাবে দ্রুত ছিল এই ঠিক,?

87
00:05:57,890 --> 00:06:02,000
পরিভাষা ইন, একত্রীকরণ সাজানোর হয় O (n log n),

88
00:06:02,000 --> 00:06:07,380
যেহেতু বুদ্বুদ সাজানোর, সন্নিবেশ সাজানোর, এবং নির্বাচন ধরণের সব হয় হে (ঢ ²).

89
00:06:07,380 --> 00:06:11,120
আসলে, যত তাড়াতাড়ি আপনি জানতে পারবেন, আপনি কেমন চিন্তা করতে পারবে না

90
00:06:11,120 --> 00:06:14,820
যে সাধারণ ক্ষেত্রে সঞ্চালিত O (n log n) চেয়ে ভাল.

91
00:06:14,820 --> 00:06:19,120
আবার, এই বড় হে স্বরলিপি সম্পর্কে এখনো যদি আপনি এটি দেখা না না দিয়ে চিন্তা করবেন.

92
00:06:19,120 --> 00:06:23,490
>> শুধু যে এই অর্থ জানা যদি আমরা একটি বড় তালিকা সাজাতে চেয়েছিলেন

93
00:06:23,490 --> 00:06:26,820
বুদ্বুদ সাজানোর, সন্নিবেশ সাজানোর, এবং নির্বাচন সাজানোর সম্ভাব্য ব্যয় হতে পারে

94
00:06:26,820 --> 00:06:29,500
সময়ের চেয়ে উল্লেখযোগ্যভাবে সাজানোর একত্রীকরণ.

95
00:06:29,500 --> 00:06:33,210
এটা যে একত্রীকরণ সাজানোর জন্য দ্রুত সব তালিকায় করা মানে এই নয়

96
00:06:33,210 --> 00:06:36,220
অথবা এমনকি জন্য কোনো একটি নির্দিষ্ট মাপ অধীন একক তালিকা.

97
00:06:36,220 --> 00:06:41,950
উদাহরণস্বরূপ, সন্নিবেশ সাজানোর সব তালিকায় 5 উপাদানের চেয়ে ছোট দ্রুততম সাজানোর জন্য হতে পারে.

98
00:06:41,950 --> 00:06:47,360
বাস্তবে, একত্রীকরণ 50 সাজানোর উপাদান হিসাবে ছোট হিসাবে তালিকার জন্য সাধারণত দ্রুত.

99
00:06:47,360 --> 00:06:51,120
>> কিন্তু এই অতিরিক্ত গতির একটি মূল্য ছাড়া আসে না.

100
00:06:51,120 --> 00:06:54,770
আমাদের অন্যান্য প্রকারের ভিন্ন, যা একটি তালিকা নিয়ে সংশোধন করতে জায়গায় তালিকা

101
00:06:54,770 --> 00:06:58,740
যতক্ষণ না আমরা একটি অনুসারে সাজানো তালিকা পেতে, একত্রীকরণ সাজানোর কিছু অতিরিক্ত স্থান প্রয়োজন

102
00:06:58,740 --> 00:07:00,900
একসাথে 2 তালিকা একত্রীকরণ.

103
00:07:00,900 --> 00:07:04,690
আমরা অবিলম্বে তালিকা যা মার্জ করা হচ্ছে না মার্জ তালিকা সংরক্ষণ ব্যবহার করতে পারেন

104
00:07:04,690 --> 00:07:08,880
যেহেতু আমরা অনেক উপাদান আছে যা এখনও করা প্রয়োজন মার্জ দ্বারা বাতিল করা হতে পারে.

105
00:07:08,880 --> 00:07:13,540
এই স্থান একটি মূল্যের একটি বিট, কিন্তু এটা সাধারণত অযৌক্তিক নয়.

106
00:07:13,540 --> 00:07:15,330
এবং যে এর একত্রীকরণ সাজানোর জন্য এটি.

107
00:07:15,330 --> 00:07:18,490
>> আমার নাম Rob Bowden, এবং এই CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- এবং সাজানোর নির্বাচন.

110
00:07:24,000 --> 00:07:25,880
[Laughs]

111
00:07:25,880 --> 00:07:31,480
ওহ, যে খুব আউট নিতে কারণ আমি সুইচ কিভাবে আমি এটি উপস্থাপনা ছিল না.

112
00:07:31,480 --> 00:07:35,680
বাম তালিকা. এটা ছিল একটা টাইপো.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] আমি মাতাল আপ -

114
00:07:39,290 --> 00:07:41,190
[Laughs]

115
00:07:41,190 --> 00:07:44,190
আমি কি জানি না -