وقتی بیش از بیست سال پیش الگوریتم هایی را مطالعه کردم ، سودمندی کلی آنها را دیدم ، اما از آن زمان تاکنون هرگز مجبور نشده ام از آنها در دنیای واقعی استفاده کنم زیرا آنها قبلاً توسط خدمات مدیریت بانک اطلاعاتی یا کارکردهای داخلی اکثر زبانهای برنامه نویسی که من استفاده می کردم ، اجرا شده بودند.
Interviewer: Can you sort this list by size?
Interviewee: Absolutely.
/types confidently.../
l.sort()
زمانی فرا رسید که مجبور شدم خودم را از الگوریتم های مرتب سازی یادآوری کنم. در اول موارد اول ، من قصد داشتم ویژگی ای را اجرا کنم که به کاربران امکان می دهد گزینه های خود را با مقایسه دو بار در یک زمان در اولویت قرار دهند. من فکر کردم که نوع حباب الگوریتم کاملاً مناسب خواهد بود.
بنابراین ، من UI را با استفاده از Reactjs و Django برای Backend ساختم تا به کاربران اجازه دهد گزینه ها را مقایسه کرده و اولویت های خود را مرتب کنند.
با این حال ، من به زودی متوجه یک مشکل شدم: برای لیست های طولانی تر ، این روند برای کاربران بسیار وقت گیر شد.
یک روز ، من چیزی راجع به پیچیدگی الگوریتم به یاد آوردم (همچنین به عنوان شناخته می شود نماد بزرگ O) و متوجه شد که نوع حباب کارآمدترین انتخاب برای این کار نیست.
در علوم کامپیوتر ، نماد بزرگ O توصیف می کند که چگونه عملکرد یک الگوریتم نسبت به اندازه ورودی رشد می کند. معمولاً مانند نوشته شده است O(value)، کجا value تابعی از nوت n تعداد مواردی است که الگوریتم فرآیند می کند.
به عنوان مثال:
- یافتن اولین مورد در یک لیست یا کلید در فرهنگ لغت N موارد است
O(1)بشر - جمع بندی همه موارد با تکرار از طریق یک لیست است
O(n)بشر - استفاده از یک حلقه توی سه گانه در لیست منجر به آن خواهد شد
O(n³)بشر
در اینجا مروری بر رایج ترین پیچیدگی ها آورده شده است:
| پیچیدگی | نام | معنی و مثال |
|---|---|---|
O(1) |
ثابت | همیشه در همان زمان ، بدون توجه به اندازه ورودی ، به عنوان مثال دسترسی به یک آرایه |
O(log n) |
لگاریتمی | اندازه دو برابر ، فقط 1 قدم ، به عنوان مثال جستجوی باینری |
O(n) |
خطی | زمان با اندازه رشد می کند ، به عنوان مثال Loop Over List |
O(n log n) |
مربوط به خطی | “تقریبا خطی” ، اما کمی کندتر ، به عنوان مثال مرتب سازی ادغام |
O(n²) |
درجه دوم | زمان با اندازه منفجر می شود ، به عنوان مثال حلقه های تو در تو در نوع حباب |
O(2ⁿ) |
نمایشی | مراقب باشید – سریع دیوانه می شود ، به عنوان مثال فیبوناچی بازگشتی |
O(n!) |
مربوط به فاکتوریل | حالت کابوس ، به عنوان مثال حل فروشنده مسافرتی توسط Brute Force |
درک عملاً بزرگ O
نوع حباب یک الگوریتم با پیچیدگی زمانی است O(n²)بشر این بدان معناست: اگر لیستی از موارد را دارید ، الگوریتم باید با استفاده از دو حلقه تو در تو ، هر مورد را در برابر بسیاری دیگر مقایسه کند.
- برای مرتب کردن لیستی از 5 مورد ، کاربر ممکن است به 25 مقایسه نیاز داشته باشد.
- برای مرتب کردن 10 مورد ، حداکثر 100 مقایسه.
- برای مرتب کردن 50 مورد ، حداکثر 2500 مقایسه.
ایده آل نیست
من از ChatGPT خواستم تا بر اساس پیچیدگی آنها ، به ارزیابی الگوریتم های مرتب سازی کمک کند ، و مرتب به عنوان یک انتخاب بسیار بهتر بیرون آمد. پیچیدگی آن است O(n log n)، کجا log n (پایه 2) تقریباً به معنی “چند بار می توانید تقسیم کنید n توسط 2 تا رسیدن به 1. “
- برای مرتب کردن 5 مورد ، مرتب سازی سریع به 12 مقایسه نیاز دارد.
- برای مرتب کردن 10 مورد ، حدود 34 مقایسه.
- برای مرتب کردن 50 مورد ، حدود 282 مقایسه.
این هنوز برخی از کار است ، اما بسیار قابل کنترل تر است.
با این حال ، از دیدگاه قابلیت استفاده ، حتی بهتر است که کاربران را به صورت دستی بکشید و وسایل خود را رها کنند یا سفارشات هوش مصنوعی را ارائه دهند. بنابراین من آن گزینه ها را نیز پیاده سازی کردم.
پیچیدگی های الگوریتم در عمل
در زیر یک برگه تقلب سریع با پیچیدگی هایی از سریعترین تا کمترین سرعت آورده شده است:
مرتب سازی الگوریتم ها
| الگوریتم | بهترین مورد | میانه | بدترین حالت | یادداشت ها |
|---|---|---|---|---|
| تیمارزورت | O(n) |
O(n log n) |
O(n log n) |
در پایتون ، جاوا استفاده می شود |
| ادغام | O(n log n) |
O(n log n) |
O(n log n) |
پایدار ، قابل اعتماد |
| مرتب | O(n log n) |
O(n log n) |
O(n log n) |
در محل |
| مرتب | O(n log n) |
O(n log n) |
O(n²) |
به طور متوسط سریعترین |
| توری | O(n log n) |
O(n¹·⁵) |
O(n²) |
درج بهبود یافته |
| مرتب سازی | O(n) |
O(n²) |
O(n²) |
برای داده های کوچک/بیشتر مرتب شده مفید است |
| نوع انتخاب | O(n²) |
O(n²) |
O(n²) |
ساده اما آهسته |
| نوع حباب | O(n) |
O(n²) |
O(n²) |
فقط برای لیست های کوچک خوب است |
الگوریتم های جستجو
| الگوریتم | بهترین مورد | میانه | بدترین حالت | یادداشت ها |
|---|---|---|---|---|
| جستجوی جدول هش | O(1) |
O(1) |
O(n) |
بدترین حالت نادر (برخورد) |
| جستجوی دودویی | O(1) |
O(log n) |
O(log n) |
به داده های مرتب شده نیاز دارد |
| جستجو | O(1) |
O(√n) |
O(√n) |
برای آرایه های مرتب شده |
| جستجوی سه گانه | O(1) |
O(log n) |
O(log n) |
به سه قسمت تقسیم شود |
| جستجوی خطی | O(1) |
O(n) |
O(n) |
بدون مرتب سازی لازم نیست ، اما کند است |
الگوریتم های رمزگذاری
| الگوریتم | پیچیدگی | یادداشت ها |
|---|---|---|
| AES (استاندارد رمزگذاری پیشرفته) |
O(1) در هر بلوک |
کلید بسیار سریع و متقارن |
| chacha20 |
O(1) در هر بلوک |
رمزنگاری مدرن ، خیلی سریع |
| رمزگذاری RSA | O(n³) |
کلید عمومی ، برای داده های بزرگ کند است |
| رمزنگاری منحنی بیضوی (ECC) | O(n²) |
سریعتر از RSA در امنیت مشابه |
| تبادل کلید Diffie-Hellman | O(n³) |
مبادله کلید ایمن ، کندتر |
فقط برای گرسنگی علاقه
Python ، MySQL و PostgreSQL از این الگوریتم ها در پشت صحنه استفاده می کنند:
| سیستم | الگوریتم مرتب سازی | یادداشت ها |
|---|---|---|
پیتون sort() وت sorted()
|
تیمارزورت | ترکیبی از نوع ادغام + مرتب سازی درج |
mysql ORDER BY
|
QuickSort (مجموعه داده های کوچک) ، ادغام یا Filesort (مجموعه داده های بزرگ) | بستگی به موتور ذخیره سازی (InnoDB و غیره) دارد |
پس از ORDER BY
|
QuickSort (داده های کوچک) ، Heapsort + Mergesort برای مجموعه های بزرگتر | سوئیچینگ هوشمند آگاهی از حافظه |
سخنان پایانی
بنابراین اگر مجبورید به جای استفاده از کتابخانه های پیش فرض – یا حتی هنگام انتخاب الگوریتم از یک کتابخانه – یک الگوریتمی مسئله توسعه را حل کنید – نماد بزرگ را به خاطر بسپاریدبشر بعضی اوقات این تفاوت می تواند میلی ثانیه یا ثانیه از زمان را صرفه جویی کند و گاهی اوقات ، هنگامی که ورودی کاربران درگیر است ، می تواند دقیقه یا حتی ساعت ها را صرفه جویی کند.
تصویر جلد توسط استیو جانسون
