1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> داگ لوید: بنابراین در CS50 ما در مورد به دست
انواع مرتب سازی و جستجو

3
00:00:08,900 --> 00:00:09,442
الگوریتم باشد.

4
00:00:09,442 --> 00:00:11,400
و گاهی اوقات می توان آن را
یک مشکل کمی برای حفظ

5
00:00:11,400 --> 00:00:14,161
آهنگ از چه الگوریتم می کند آنچه.

6
00:00:14,161 --> 00:00:15,910
ما واقعا تنها
خامه سطح بیش از حد،

7
00:00:15,910 --> 00:00:18,740
بسیاری از جستجوی دیگر وجود دارد
و مرتب سازی الگوریتم باشد.

8
00:00:18,740 --> 00:00:21,780
بنابراین در این فیلم اجازه دهید
فقط چند دقیقه طول می کشد

9
00:00:21,780 --> 00:00:24,980
را امتحان کنید و تقطیر هر الگوریتم
به عناصر اصلی آن

10
00:00:24,980 --> 00:00:27,810
بنابراین شما می توانید به یاد داشته باشید ترین
اطلاعات مهم در مورد آنها

11
00:00:27,810 --> 00:00:31,970
و قادر به بیان
تفاوت ها، در صورت لزوم.

12
00:00:31,970 --> 00:00:34,220
>> اولین مرتب سازی انتخابی است.

13
00:00:34,220 --> 00:00:38,210
ایده اصلی در پشت مرتب سازی انتخابی
است پیدا کردن کوچکترین عنصر نامرتب

14
00:00:38,210 --> 00:00:42,890
در یک آرایه و آن را مبادله با
اولین عنصر آرایه نامرتب از که.

15
00:00:42,890 --> 00:00:46,620
ما گفت که بدترین حالت
زمان اجرا که N مربع بود.

16
00:00:46,620 --> 00:00:50,060
و اگر شما می خواهید به یاد چرا، را
نگاهی به فیلم مرتب سازی انتخابی است.

17
00:00:50,060 --> 00:00:54,560
در بهترین حالت زمان اجرا
همچنین N مربع.

18
00:00:54,560 --> 00:00:58,910
>> حباب مرتب سازی بر، ایده پشت این
یکی است که به مبادله جفت های مجاور.

19
00:00:58,910 --> 00:01:01,730
به طوری که کلیدی است که شما کمک می کند را
به یاد داشته باشید تفاوت در اینجا.

20
00:01:01,730 --> 00:01:04,920
مرتب سازی انتخابی است، تا کنون،
پیدا کردن حباب smallest--

21
00:01:04,920 --> 00:01:06,790
مرتب کردن بر اساس مبادله جفت های مجاور.

22
00:01:06,790 --> 00:01:08,710
ما مبادله جفت های مجاور
از عناصر اگر آنها

23
00:01:08,710 --> 00:01:12,530
خارج از دستور، که به طور موثر
حباب عناصر بزرگتر به سمت راست،

24
00:01:12,530 --> 00:01:17,060
و در همان زمان آن را نیز آغاز می شود
به حرکت عناصر کوچکتر به سمت چپ.

25
00:01:17,060 --> 00:01:20,180
بدترین حالت زمان مورد اجرا
از مرتب سازی حبابی است N مربع.

26
00:01:20,180 --> 00:01:23,476
در بهترین حالت زمان اجرا
از حباب مرتب سازی بر است N.

27
00:01:23,476 --> 00:01:25,350
از آنجا که در این وضعیت
ما actually-- نیست

28
00:01:25,350 --> 00:01:27,141
ما ممکن است نیاز به
هر گونه معاوضه در همه.

29
00:01:27,141 --> 00:01:31,026
ما فقط باید برای ساختن یک
تصویب در تمام عناصر N.

30
00:01:31,026 --> 00:01:34,600
>> در مرتب سازی بر درج،
ایده اصلی در اینجا در حال تغییر است.

31
00:01:34,600 --> 00:01:36,630
که کلمه کلیدی برای مرتب سازی درجی است.

32
00:01:36,630 --> 00:01:39,630
ما در حال رفتن به مرحله یک بار از طریق
آرایه از چپ به راست.

33
00:01:39,630 --> 00:01:41,670
و همانطور که ما انجام دهید، ما
رفتن به تغییر عناصر

34
00:01:41,670 --> 00:01:46,260
ما در حال حاضر دیده می شود به اتاق را برای
کوچکتر که نیاز به جا به جایی

35
00:01:46,260 --> 00:01:48,080
در آن بخش طبقه بندی شده اند.

36
00:01:48,080 --> 00:01:51,600
بنابراین ما ساخت یک آرایه مرتب شده
عنصر در یک زمان، چپ به راست،

37
00:01:51,600 --> 00:01:54,740
و ما تغییر همه چیز را به اتاق.

38
00:01:54,740 --> 00:01:58,650
بدترین حالت زمان اجرا از
مرتب سازی بر درج شده است N مربع.

39
00:01:58,650 --> 00:02:02,380
ساعت هم بهترین حالت اجرا است N.

40
00:02:02,380 --> 00:02:05,380
>> ادغام sort-- کلمه کلیدی
در اینجا تقسیم و ادغام.

41
00:02:05,380 --> 00:02:08,949
ما تقسیم آرایه کامل، چه
آن را شش عنصر، هشت عنصر،

42
00:02:08,949 --> 00:02:13,790
10،000 elements-- ما آن را تقسیم
پایین به نصف، نصف، نصف،

43
00:02:13,790 --> 00:02:17,720
تا زمانی که ما تحت آرایه دارند
از n یک آرایه عنصر.

44
00:02:17,720 --> 00:02:19,470
مجموعه ای از N یک آرایه عنصر.

45
00:02:19,470 --> 00:02:22,640
بنابراین ما با یک آغاز شده
آرایه 1،000 عنصر،

46
00:02:22,640 --> 00:02:26,550
و ما به نقطه که در آن ما
1،000 آرایه یک عنصر است.

47
00:02:26,550 --> 00:02:30,990
پس از آن ما شروع به ادغام آن زیر آرایه
تماس با هم در جهت درست.

48
00:02:30,990 --> 00:02:34,860
بنابراین ما دو آرایه یک عنصر
و ایجاد یک آرایه دو عنصر است.

49
00:02:34,860 --> 00:02:38,180
ما را دو آرایه دو عنصر
و ایجاد یک آرایه چهار عنصر

50
00:02:38,180 --> 00:02:43,900
و به همین ترتیب و تا زمانی که ما این
دوباره بازسازی یک آرایه از عناصر N.

51
00:02:43,900 --> 00:02:48,410
>> بدترین حالت زمان اجرا از
ادغام مرتب کردن بر اساس n بار log n است.

52
00:02:48,410 --> 00:02:52,390
ما عناصر N، اما
این فرایند ترکیب مجدد

53
00:02:52,390 --> 00:02:56,960
طول می کشد log n است مراحل دریافت
به یک آرایه کامل برگشت.

54
00:02:56,960 --> 00:03:01,160
بهترین حالت زمان اجرا نیز N ورود به سیستم
N چرا که این فرآیند واقعا نمی

55
00:03:01,160 --> 00:03:04,090
مراقبت که آیا آرایه بود
طبقه بندی شده اند و یا برای شروع با است.

56
00:03:04,090 --> 00:03:07,590
این روند همان است، وجود دارد
هیچ راهی برای چیزهایی اتصال کوتاه.

57
00:03:07,590 --> 00:03:11,610
بنابراین n log n استفاده در بدترین حالت،
n log n استفاده در بهترین حالت.

58
00:03:11,610 --> 00:03:13,960
>> ما در مورد دو صحبت
جستجو الگوریتم.

59
00:03:13,960 --> 00:03:16,230
بنابراین جستجوی خطی است که در مورد تکرار.

60
00:03:16,230 --> 00:03:19,500
ما در سراسر آرایه ادامه
یک بار، از چپ به راست،

61
00:03:19,500 --> 00:03:21,950
تلاش برای پیدا کردن تعداد
که ما دنبال آن هستید.

62
00:03:21,950 --> 00:03:24,550
ساعت هم بدترین حالت اجرا O بزرگ از n است.

63
00:03:24,550 --> 00:03:27,610
این ممکن است ما را تکرار
در سراسر هر عنصر

64
00:03:27,610 --> 00:03:30,660
برای پیدا کردن عنصر ما به دنبال
برای، چه در موقعیت و زمان آخرین،

65
00:03:30,660 --> 00:03:31,630
یا نه در همه.

66
00:03:31,630 --> 00:03:34,720
اما ما نمی توانیم تا زمانی که تایید می کنند که
ما همه چیز را کرده ام.

67
00:03:34,720 --> 00:03:36,730
متر در بهترین حالت، ما بلافاصله پیدا کنید.

68
00:03:36,730 --> 00:03:41,060
در بهترین حالت زمان اجرا از
جستجوی خطی امگا، از مجموع 1 است.

69
00:03:41,060 --> 00:03:43,689
>> در نهایت، بود جستجوی دودویی وجود دارد،
که نیاز به آرایه های همه فن حریف.

70
00:03:43,689 --> 00:03:45,605
به یاد داشته باشید که بسیار
توجه مهم

71
00:03:45,605 --> 00:03:47,155
در هنگام کار با جستجوی دودویی.

72
00:03:47,155 --> 00:03:50,180
این یک پیش نیاز به استفاده it--
آرایه که شما به دنبال از طریق

73
00:03:50,180 --> 00:03:52,160
باید طبقه بندی شده اند.

74
00:03:52,160 --> 00:03:54,500
در غیر این صورت، کلمه کلیدی
تقسیم و حل است.

75
00:03:54,500 --> 00:03:58,310
تقسیم این آرایه را به نصف و
از بین بردن نیمی از عناصر

76
00:03:58,310 --> 00:04:00,780
هر بار که شما ادامه از طریق.

77
00:04:00,780 --> 00:04:04,330
از آنجا که این تقسیم و حل
و چیزهای تقسیم در نیمه رویکرد،

78
00:04:04,330 --> 00:04:07,450
بدترین حالت زمان اجرا
از جستجوی دودویی است

79
00:04:07,450 --> 00:04:11,730
log n است، که قابل ملاحظه است
بهتر از N جستجوی خطی است.

80
00:04:11,730 --> 00:04:13,570
ساعت هم بهترین حالت اجرا هنوز هم یکی.

81
00:04:13,570 --> 00:04:17,010
>> ما ممکن است آن را بلافاصله پیدا
اولین بار که ما را یک تقسیم، اما،

82
00:04:17,010 --> 00:04:19,339
دوباره، به یاد داشته باشید که
اگرچه جستجوی دودویی است

83
00:04:19,339 --> 00:04:24,030
قابل ملاحظه ای بهتر از جستجوی خطی
به خاطر اینکه ورود N در برابر N،

84
00:04:24,030 --> 00:04:27,110
شما ممکن است از طریق کار به
مرتب سازی آرایه خود را برای اولین بار است که

85
00:04:27,110 --> 00:04:32,010
ممکن است آن را کمتر بسته موثر
به اندازه از تکرار طبقه بندی شده اند.

86
00:04:32,010 --> 00:04:35,250
>> من داگ لوید هستم، این CS50.

87
00:04:35,250 --> 00:04:36,757