[Powered by Google Translate] شما احتمالا شنیده مردم صحبت در مورد یک الگوریتم سریع و کارآمد برای اجرای وظیفه خاص خود را، اما آنچه که دقیقا می کند آن را برای یک الگوریتم سریع و کارآمد چیست؟ خوب، آن را در مورد اندازه گیری را در زمان واقعی صحبت نمی کنم، مثل ثانیه یا دقیقه. دلیل این است که سخت افزار کامپیوتر و نرم افزار به شدت متفاوت است. برنامه ممکن است اجرای آهسته تر از مال شما، چون من آن را در حال اجرا بر روی یک کامپیوتر قدیمی تر و یا به خاطر اینکه من اتفاق می افتد به بازی بازی های ویدئویی آنلاین در همان زمان، که خمیدگی تمام حافظه من، و یا ممکن است در حال اجرا برنامه از طریق نرم افزار های مختلف که ارتباط با دستگاه در سطح پایین متفاوت است. این مثل مقایسه سیب و پرتقال است. فقط به خاطر کندتر کامپیوتر من طول می کشد از مال شما را به جواب به این معنا نیست که شما باید الگوریتم کارآمد تر. 

بنابراین، از آنجایی که ما به طور مستقیم نمی تواند مقایسه زمان های اجرا از برنامه ها در عرض چند ثانیه یا چند دقیقه، چگونه 2 الگوریتم های مختلف را با هم مقایسه کرد صرف نظر از سخت افزار خود و یا محیط نرم افزاری؟ برای ایجاد یک راه یکنواخت تر از اندازه گیری بهره وری الگوریتم، دانشمندان کامپیوتر و ریاضی ابداع کرده اند مفاهیم برای اندازه گیری پیچیدگی یک الگوریتم و نماد به نام 'بزرگ Ohnotation' برای توصیف این. تعریف رسمی این است که یک تابع f (x) قابل اجرا بر روی منظور از G (X) اگر وجود دارد برخی از ارزش (x) وجود دارد، X ₀ و برخی از ثابت، C، که F (x) کمتر از یا مساوی با که بار ثابت G (x) برای تمام x های بزرگتر از X ₀. 

اما نمی شود تعریف رسمی دور می ترسم. چه این در واقع در کمتر قوانین و مقررات نظری چیست؟ خوب، آن را اساسا یک روش تجزیه و تحلیل با چه سرعتی در زمان اجرا یک برنامه مجانبی رشد می کند. این است که، به عنوان اندازه از ورودی های خود را به سمت بی نهایت افزایش می یابد، می گویند، شما در حال مرتب سازی یک آرایه از اندازه 1000 در مقایسه به آرایه ای از اندازه 10. زمان اجرای برنامه خود را چگونه رشد می کنند؟ به عنوان مثال، تصور کنید که شمارش تعدادی از شخصیت های در یک رشته ساده ترین راه  با راه رفتن را از طریق تمام رشته نامه های نامه و اضافه کردن 1 به یک شمارنده برای هر یک از شخصیت. گفته شده است که این الگوریتم را در زمان خطی اجرا با توجه به تعدادی از شخصیت های، 'N' در رشته. به طور خلاصه، آن را در O (N) را اجرا می کند. چرا این است که است؟ خوب، با استفاده از این روش، زمان مورد نیاز برای گذشتن از تمام رشته متناسب با تعداد حروف است. شمارش تعداد کاراکتر در یک رشته 20 کاراکتری رفتن را به دو برابر زمانی که آن را طول می کشد به تعداد کاراکتر در یک رشته 10 کاراکتری، دلیل این که شما را در تمام شخصیت های و هر یک از شخصیت طول می کشد همان مقدار از وقت را به نگاه در. همانطور که تعدادی از کاراکتر ها افزایش می یابد، در زمان اجرا به صورت خطی با افزایش طول ورودی. 

در حال حاضر، تصور کنید اگر شما تصمیم می گیرید که زمان خطی، O (N)، فقط به اندازه کافی سریع برای شما نیست؟ شاید شما ذخیره سازی رشته های بزرگ، و شما می توانید زمان بیشتری آن را انجام دهید را ندارند برای گذشتن از همه از شخصیت های خود را شمارش یک و یک. بنابراین، شما تصمیم می گیرید سعی کنید چیزی متفاوت است. چه می شود اگر شما اتفاق می افتد را به تعدادی از شخصیت های در حال حاضر ذخیره در رشته، می گویند، در یک متغیر به نام «لن، در اوایل برنامه، قبل از اینکه شما حتی شخصیت بسیار برای اولین بار در رشته خود را ذخیره می شود؟ سپس، همه شما می خواهم که برای انجام این کار در حال حاضر برای پیدا کردن طول رشته در است بررسی کنید چه مقدار متغیر است. شما نمی خواهد که به رشته خود را در تمام نگاه، و دسترسی به مقدار یک متغیر مانند لن در نظر گرفته شده است زمان عمل مجانبی ثابت، O (1) است. چرا این است که است؟ خب، به یاد داشته باشید آنچه که پیچیدگی مجانبی به این معنی است. چگونه تغییر می کند در زمان اجرا به عنوان اندازه ورودی شما رشد می کند؟ 

می گویند شما که در تلاش برای بدست آوردن تعداد کاراکتر در یک رشته بزرگتر است. خوب، آن را نمی خواهد مهم نیست چقدر بزرگ شما را به رشته، حتی یک میلیون کاراکتر، همه شما می خواهم که برای انجام این کار برای پیدا کردن طول رشته را با این رویکرد، برای خواندن مقدار متغیر لن، که شما در حال حاضر ساخته شده است. طول ورودی است، که، طول رشته شما در حال تلاش برای پیدا کردن، چگونه سریع برنامه خود را اجرا می کند تاثیر نمی گذارد. این بخشی از برنامه های خود را اجرا کنید به همان اندازه سرعت بر روی یک رشته از یک شخصیت و یک هزار کاراکتر رشته، و به همین دلیل این برنامه را می توان به عنوان در حال اجرا در زمان ثابت می گویند با توجه به اندازه ورودی است. 

البته، یک نقطه ضعف وجود دارد. شما صرف فضای حافظه اضافی بر روی کامپیوتر شما ذخیره سازی متغیر و زمان اضافی آن را به شما قرار می گیرد برای انجام ذخیره سازی واقعی متغیر، اما نکته هنوز هم می ایستد، پیدا کردن چه مدت طول رشته شما در طول رشته در همه بستگی ندارد. بنابراین، آن را در O (1) و یا زمان ثابت اجرا می شود. این قطعا به این معنا نیست که کد شما را اجرا می کند در 1 مرحله، اما مهم نیست که چگونه بسیاری از مراحل آن است، اگر آن را با اندازه ورودی را تغییر دهید، آن هنوز مجانبی ثابت است که ما به عنوان O (1) نشان دهنده. 

همانطور که شما احتمالا می توانید حدس بزنید، های مختلف از زمان های اجرا O بزرگ برای اندازه گیری الگوریتم با وجود دارد. O (n) ² الگوریتم های مجانبی کندتر از O (n) الگوریتم است. این است که، به عنوان تعدادی از عناصر (N) رشد می کند، در نهایت O (N) ² الگوریتم های زمان بیشتری را از الگوریتم O (n) را اجرا کنند. این به این معنا نیست که الگوریتم O (n) همیشه اجرای سریع تر از O (n) ² الگوریتم، حتی در همان محیط، در همان سخت افزار است. شاید برای اندازه ورودی کوچک،  O (n) ² الگوریتم در واقع ممکن است سریعتر کار می کنند، اما، در نهایت، به عنوان اندازه ورودی را افزایش می دهد به سمت بی نهایت، زمان اجرا O (N) الگوریتم ² در نهایت در زمان اجرا از الگوریتم O (N) را تحت الشعاع قرار. درست مانند هر تابع درجه دوم ریاضی  سرانجام سبقت گرفتن هر تابع خطی، هیچ مهم نیست که چه مقدار از سر شروع تابع خطی شروع می شود. اگر شما در حال کار با مقادیر زیادی از داده ها، الگوریتم که در O (N) زمان ² واقعا می تواند تا پایان کاستن از سرعت برنامه های خود را، اما برای اندازه ورودی کوچک، شما احتمالا حتی توجه نکردین. 

یکی دیگر از پیچیدگی مجانبی است، لگاریتمی زمان، O (log n است). نمونه ای از یک الگوریتم اجرا می شود که این سرعت کلاسیک الگوریتم جستجوی دودویی، برای پیدا کردن یک عنصر در یک لیست در حال حاضر مرتب شده از عناصر. 

اگر شما نمی دانید که چه دودویی جستجو می کند، من آن را برای شما توضیح داده واقعا به سرعت. بیایید می گویند شما دنبال آن هستید را برای شماره 3 در این آرایه ای از اعداد صحیح است. آن را در عنصر وسط آرایه به نظر می رسد و می پرسد، "آیا عنصر من می خواهم بیشتر از، برابر، و یا کمتر از این است؟" اگر آن برابر است، پس از آن بزرگ است. شما را در بر داشت این عنصر، و شما انجام می شود. اگر آن را بیشتر، و سپس شما می دانید این عنصر در سمت راست از آرایه باشد، و شما فقط می توانید در آن در آینده نگاه کنید، و اگر آن را کوچکتر، و سپس شما می دانید آن را به در سمت چپ باشد. این فرایند پس از آن با آرایه های کوچکتر به اندازه تکرار تا زمانی که این عنصر درست می شود. 

این الگوریتم قدرتمند کاهش اندازه آرایه در نصف با هر عمل است. بنابراین، برای پیدا کردن یک عنصر در یک آرایه مرتب از اندازه 8، در اکثر (ورود ₂ 8) یا 3 از این عملیات، بررسی عنصر میانی، و سپس برش آرایه در نصف خواهد شد. در حالی که یک آرایه از اندازه 16 طول می کشد (ورود ₂ 16) یا 4 عملیات. که فقط 1 عمل بیشتر برای یک آرایه دو برابر اندازه. دو برابر اندازه آرایه زمان اجرا را افزایش می دهد توسط تنها 1 تکه از این کد. دوباره، چک کردن عنصر وسط لیست، پس از آن تقسیم است. بنابراین، این گفت: در زمان لگاریتمی عمل، O (ورود N). اما صبر کنید، به شما می گویند، آیا این بستگی دارد که در لیست این عنصر است که شما به دنبال آن هستید؟ اگر اولین عنصر در نگاه اتفاق می افتد که یکی از سمت راست است؟ سپس، آن را تنها طول می کشد 1 عملیات، مهم نیست چقدر بزرگ لیست می باشد. 

خب، به همین دلیل است که دانشمندان کامپیوتر قوانین و مقررات پیچیدگی مجانبی است که منعکس کننده بهترین حالت و بدترین حالت اجرای الگوریتم. به درستی، از مرزهای بالایی و پایینی در زمان اجرا است. در بهترین حالت برای جستجوی دودویی عنصر ما درست در وسط وجود دارد، و شما آن را در زمان ثابت، مهم نیست چقدر بزرگ بقیه از آرایه است. نماد مورد استفاده برای این Ω است. بنابراین، این الگوریتم گفته شده است به اجرا در Ω (1). در بهترین حالت آن را پیدا کرد، این عنصر به سرعت، مهم نیست چقدر بزرگ آرایه، اما در بدترین حالت، آن را به انجام (ورود N) تقسیم چک از آرایه به پیدا کردن عنصر سمت راست است. بدترین حالت بالای مرزهای بزرگ "O" است که شما در حال حاضر می دانیم نامیده می شود. بنابراین، آن O (log n است)، اما Ω (1) است. 

جستجو خطی در مقابل، که در آن شما را از طریق هر عنصر از آرایه به راه رفتن برای پیدا کردن یکی از شما می خواهم، در بهترین حالت Ω (1). باز هم، اولین عنصری است که شما می خواهید. بنابراین، مهم نیست که چقدر بزرگ آرایه است. در بدترین حالت، آن است که آخرین عنصر در آرایه. بنابراین، شما باید راه رفتن را از طریق تمام عناصر ازت در آرایه به آن را پیدا کنید، دوست دارم اگر از 3 به دنبال شد. بنابراین، آن را در O (n) مدت زمان اجرا می شود به دلیل آن متناسب با تعداد عناصر موجود در آرایه. 

یکی دیگر از نماد استفاده شده است Θ. این را می توان مورد استفاده قرار گیرد برای توصیف الگوریتم های که در آن بهترین و بدترین موارد یکسان هستند. این در مورد الگوریتم طول رشته ما صحبت در مورد قبل از آن است. به این معنا که اگر ما آن را در یک متغیر ذخیره قبل از ما این رشته و بعد از آن در زمان ثابت به آن دسترسی داشته باشید. مهم نیست که چه تعداد ما در حال ذخیره سازی در آن متغیر، ما باید به آن نگاه کنید. بهترین حالت این است که ما به آن نگاه کنید پیدا کردن طول رشته است. پس Ω (1) و یا در مورد بهترین زمان ثابت است. بدترین حالت این است، ما به آن نگاه کنید و پیدا کردن طول رشته. بنابراین، O (1) و یا ثابت زمانی در بدترین حالت است. بنابراین، از آنجا که بهترین حالت و بدترین موارد هستند، این را می توان گفت که در Θ (1) زمان اجرا شود. 

به طور خلاصه، ما باید راه های خوب به همین دلیل در مورد بهره وری کدهای بدون نیاز به دانستن هر چیزی در مورد زمان در دنیای واقعی آنها را برای اجرا، است که بسیاری از عوامل خارجی تحت تاثیر قرار، از جمله متفاوت سخت افزار، نرم افزار، یا ویژگی های کد شما. همچنین، این به ما اجازه می دهد به همین دلیل به خوبی در مورد آنچه اتفاق خواهد افتاد وقتی اندازه ورودی را افزایش می دهد. 

اگر شما در حال اجرا در O (N) ² الگوریتم، و یا بدتر از آن، O (2 ⁿ) الگوریتم، یکی از سریع ترین انواع رو به رشد، شما واقعا می خواهید رکود به اطلاع هنگامی که شما شروع به کار با مقادیر بیشتری از داده ها است. 

این پیچیدگی مجانبی است. با تشکر.