[Powered by Google Translate] Siz yəqin ki, insanların sürətli və ya səmərəli alqoritm haqqında danışmaq duydum xüsusi tapşırığı yerinə ki, lakin bu sürətli və ya səmərəli olması üçün alqoritm üçün dəqiq nə deməkdir? Bəli, bu, real vaxt bir ölçü söhbət deyil saniyə və ya dəqiqə kimi. Çünki kompüter hardware və proqram kəskin dəyişir. Mənim proqram, sizin ləng run bilər Mən köhnə kompüter üzrə çalışan alıram çünki və ya bir online video oyun oynayan üçün baş, çünki eyni zamanda, bu, bütün yaddaş hogging olunur və ya müxtəlif proqram vasitəsilə mənim proqram çalışan bilər bir aşağı səviyyədə fərqli maşın ilə əlaqələndirir. Bu alma və portağal müqayisə kimi. Mənim yavaş kompüter uzun çəkir Məhz sizin cavab geri vermək çox Siz daha səmərəli alqoritm var demək deyil. 

Belə ki, biz birbaşa proqramları runtimes müqayisə bilməz ildən saniyə və ya dəqiqə, necə 2 müxtəlif alqoritmləri müqayisə yoxdur asılı olmayaraq, hardware və ya proqram ətraf mühit? Alqoritmik səmərəliliyinin qiymətləndirilməsi bir daha forma yol yaratmaq üçün kompüter alim və riyaziyyatçılar devised var bir proqram asimptotik mürəkkəblik ölçülməsi üçün anlayışlar və notation 'Big Ohnotation "adlı Bu təsvir. Rəsmi definition bir funksiyası f (x) g sifarişi (x) çalışır bəzi (x) dəyəri var, əgər x ₀ və bəzi daimi, C, üçün f (x)-dən az və ya bərabər ki, daimi dəfə g (x) x ₀ daha bütün x. 

Amma formal tərifi ilə üz qorxuram olmayın. Bu, həqiqətən, nəzəri baxımından az nə deməkdir? Bəli, bu əsasən təhlil yolu var bir proqramın iş asimptotik artır necə sürətli. Sizin vəsaitlərin həcmi sonsuzluğa doğru artır ki, edir söz, siz ölçüsü 10 bir sıra müqayisədə ölçüsü 1000 bir sıra çeşidlənməsi edirik. Sizin proqram iş necə inkişaf edir? Məsələn, simvol sayını hesablamaq təsəvvür simli ən sadə yolu  bütün cərgə ilə gəzinti ilə məktub-by-məktub və hər bir xarakter üçün counter 1 əlavə. Bu alqoritm Xətti zaman çalışır deyilir simvolların sayı ilə əlaqədar, Simli ildə 'n'. Qısa olaraq, O (n) çalışır. Niyə bu? Bəli, bu yanaşma istifadə edərək, zaman tələb bütün simli axır etmək simvolların sayını orantılıdır. 20 xarakter string simvol sayı hesablanması edir kimi iki dəfə kimi uzun gedir 10 xarakter string olan simvol saymaq, bütün simvol baxmaq, çünki və hər bir xarakter baxmaq eyni məbləği alır. Siz simvolların sayını artırmaq kimi, Runtime giriş uzunluğu xətti artacaq. 

Əgər xətti vaxt qərar varsa, təsəvvür O (n), yalnız kifayət qədər sürətli sizin üçün deyil? Bəlkə, böyük strings saxlanılması edirik və bunu görəcək əlavə vaxt ödəyə bilməz bir-bir hesablama onların simvol bütün axır etmək. Belə ki, fərqli bir cəhd qərar. Nə artıq simvolların sayını saxlamaq olur əgər simli ildə, 'len "adlı dəyişən, demək erkən proqram üzrə, Siz simli çox ilk xarakter saxlanılır əvvəl? Sonra bütün siz string uzunluğu tapmaq üçün indi nə etmək istiyorum dəyişən dəyəri nə kontrol edir. Siz, bütün simli özü baxmaq olmazdı və len kimi bir dəyişən dəyəri daxil hesab edilir bir asimptotik daimi dəfə əməliyyat, və ya O (1). Niyə bu? Yaxşı, asimptotik mürəkkəblik nə deməkdir xatırlayıram. Necə ölçüsü kimi iş dəyişiklik yoxdur Sizin giriş artır? 

Bir böyük simli simvol sayı almaq üçün çalışdıqlarını deyirlər. Bəli, bu, siz string etmək necə böyük məsələ deyil hətta bir milyon simvol uzun, bütün bu yanaşma ilə simli uzunluğu tapmaq üçün nə etmək istiyorum , dəyişən len dəyəri oxuyub üçün siz artıq təşkil edib. Ki, daxil uzunluğu tapa çalışdığınız simli uzunluğu, Proqram çalışır necə sürətli bütün təsir etmir. Proqram bu hissəsi bir xarakter string haqqında bərabər sürətli çalışır və min xarakter simli, Bu proqram sabit zaman çalışır kimi istinad olunacaq niyə və ki daxil ölçüsü ilə bağlı. 

Əlbəttə ki, bir günah yoxdur. Siz kompüter əlavə yaddaş alanı sərf dəyişən saxlanılması və sizi əlavə vaxt dəyişən faktiki storage etmək üçün, lakin baxımından hələ dayanır, sizin simli necə uzun tapmaq bütün simli müddəti asılı deyil. Belə ki, O (1) və ya daimi zaman çalışır. Bu, əlbəttə, demək yoxdur Sizin kodu, 1 addım çalışır amma nə qədər çox addımlar ki, bu vəsaitlərin ölçüsü dəyişə deyilsə, hələ biz O (1) kimi təmsil asimptotik daimi var. 

Yəqin ki, tapmaq kimi, ilə alqoritmlər ölçmək üçün bir çox müxtəlif böyük O runtimes var. O (n) ² alqoritmlər O (n) alqoritmlər çox asimptotik yavaş var. Elementlərinin sayı (n) artır ki, edir nəhayət O (n) ² alqoritmləri daha çox vaxt aparacaq O (n) alqoritmlər çalıştırmak üçün çox. Bu O (n) alqoritmlər həmişə daha sürətli run demək deyil O (n) ² alqoritmlərin çox, hətta eyni mühitdə, Eyni hardware. Bəlkə kiçik giriş ölçüləri üçün,  O (n) ² alqoritm əslində, daha sürətli iş bilər amma, nəhayət, giriş ölçüsü artırır sonsuzluğa doğru, O (n) ² alqoritm nin iş nəticədə O (n) alqoritmi Runtime geridə qoya edəcək. Hər hansı bir kvadrat riyazi funksiyası kimi  nəticədə hər linear function keçəcəyi təxmin edilir, nə qədər baş linear function başlamaq heç bir məsələ ilə off başlayır. Siz məlumatın böyük həcmdə iş edirsinizsə O çalışır ki, alqoritmlər (n) ² zaman, həqiqətən, proqram yavaşlatan başa bilər lakin kiçik giriş ölçüləri üçün, yəqin ki, qeyd belə deyil. 

Digər asimptotik mürəkkəblik edir logarithmic zaman, O (Giriş n). Tez bu çalışır ki, bir alqoritm nümunəsi , klassik ikili axtarış alqoritm edir elementlərinin artıq sıralaması siyahısında bir element tapmaq üçün. 

Siz ikili axtarış nə bilmirsinizsə, Mən, həqiqətən, tez sizin üçün izah edəcəyik. Deyək ki sayı 3 aradığınız demək integers bu sıra. Bu serialın orta element baxır və "Mən daha çox istədiyiniz element deyil, bərabər və ya bu az?" soruşur, O böyük, bərabər varsa. Siz element aşkar və siz tamamlayın. Daha çox varsa, onda siz element bilirik , serialın sağ tərəfində olmalıdır və yalnız gələcəkdə baxmaq olar bu kiçik varsa və sonra onu sol tərəfində olmalıdır bilirik. Bu proses sonra kiçik ölçülü array ilə təkrar olunur düzgün element aşkar qədər. 

Bu güclü alqoritmi hər əməliyyat yarısında array ölçüsü azalıb. Belə ki, ölçüsü 8-sıralanır array bir element tapmaq, ən çox (₂ 8 daxil) bu əməliyyatların və ya 3, orta element yoxlanılması, sonra yarısında array kəsmə, tələb olunacaq ölçüsü 16 bir sıra (₂ 16 daxil) alır, halbuki və ya 4 əməliyyatları. Bu yalnız bir iki dəfə ölçülü array üçün 1 daha əməliyyatı. Serialın ölçüsü katlama bu kodu yalnız 1 yığın tərəfindən uzunluğu artır. Yenə sonra bölünmə, siyahıda orta element yoxlanılması. Belə ki, o, logarithmic vaxt fəaliyyətə deyilir O (Giriş n). Lakin, demək, gözləyin siyahıda aradığınız element olduğu bu asılı deyil? Nə əgər baxmaq ilk element sağ olmaq olur? Sonra o, yalnız, 1 əməliyyat görür siyahısında nə qədər böyük olursa olsun. 

Kompüter alimləri daha baxımından niyə Yaxşı, ki ən yaxşı halda əks etdirən asimptotik mürəkkəbliyi üçün və ən pis halda bir alqoritm çıxışları. Daha düzgün, yuxarı və aşağı həddi Runtime haqqında. Binar axtarış üçün ən yaxşı halda, bizim element orada ortasında, və siz daimi vaxtında almaq serialın qalan nə qədər böyük olursa olsun. Bu istifadə rəmzi Ω edir. Belə ki, bu alqoritm Ω (1) çalışması edir. Ən yaxşı halda, o, tez element hesab serialın nə qədər böyük olursa olsun, amma ən pis halda, o (Giriş n) split çek çıxış edir serialın hüququ element tapa bilərsiniz. Ən pis halda yuxarı həddi artıq bilirəm ki, böyük "O" ilə aid edilir. Belə ki, O (Giriş n), lakin Ω (1) var. 

A xətti axtarış, əksinə, Siz array hər element vasitəsilə gəzmək olan istədiyiniz tapmaq, yaxşı Ω (1) edir. Yenə ilk element istədiyiniz. Belə ki, serialın nə qədər böyük əhəmiyyətli deyil. Ən pis halda, serialın son element var. Belə ki, siz tapmaq üçün array bütün n elementləri vasitəsilə gəzmək üçün siz 3 axtarır, əgər istəyirəm. Belə ki, O (n) zaman çalışır bu sıra elementlərinin sayına mütənasib hissəsi çünki. 

Istifadə daha bir simvolu Θ edir. Bu harada ən yaxşı və ən pis halda alqoritmlər təsvir etmək üçün istifadə edilə bilər eynidir. Bu əvvəllər danışdı string uzunluğu alqoritmlər olduğu. Biz əvvəl bir dəyişən bu saxlamaq əgər ki, biz simli saxlamaq və sonra sabit zaman daxil. Nə sayı olmayaraq biz dəyişən saxlanılması edirik, biz baxmaq lazımdır. Ən yaxşı halda, biz baxmaq və simli uzunluğu tapa bilərsiniz. Ω (1) və ya ən yaxşı halda daimi vaxt belə. Ən pis halda ki, biz baxmaq və simli uzunluğu tapa bilərsiniz. Belə ki, O (1) və ya ən pis halda daimi vaxt. Belə ki, ən yaxşı halda və ən pis hallarda ildən, eyni bu Θ (1) vaxt run deyilə bilər. 

Beləliklə, biz kodları səmərəliliyi haqqında səbəbdən yaxşı yolu var onlar run etmək üçün real dünya vaxt haqqında heç bir şey bilmədən, ki, kənar amillər çox təsir edir müxtəlif hardware, proqram, o cümlədən və ya kodu xüsusiyyətləri. Həmçinin, bu, bizə nə olacaq haqqında Səbəb imkan verir zaman giriş artır ölçüsü. 

Ey (n) ² alqoritmi, çalışan istəyirsinizsə və ya pis bir O (2 ⁿ) alqoritmi, ən sürətlə inkişaf edən növlərindən biridir, həqiqətən azalması qeyd başlamaq lazımdır siz məlumatın böyük məbləğlər ilə iş başlamaq zaman. 

Bu asimptotik mürəkkəblik var. Thanks.