Alqoritmlər və onların mürəkkəbliyini necə təhlil etmək

Alqoritmlər gündəlik həyata keçirdiyimiz bütün işlərdə iştirak edir. Onların bir çoxunu "avtomatik" olaraq yerinə yetiririk, hətta onların nə üçün istifadə edildiyini və "necə" istifadə etdiyimizi bilmədən. Proqram inkişafında o qədər də fərqli deyil. Bəs alqoritmlər nədir? Onların mürəkkəbliyini təhlil etmək niyə vacibdir?

Gəlin öyrənək! :)

Bir alqoritm nədir?

Bir tapşırıq yerinə yetirmək üçün lazımlı addımlar toplusu.

Kompüter proqramları alqoritmləri yerinə yetirən tək şey deyil, həm də insanlar tərəfindən icra olunur və tətbiq olunur.

Məsələn, aşağıdakı vəzifələri icra edən alqoritm barədə düşünmüsünüz?

  • Dişlərini fırçala
  • Duş qəbul etmək
  • Bişirin
  • Evdən işləmək üçün sürün

Günümüzdə yuxarıda göstərilən vəzifələrdən ən az birini yerinə yetirmək üçün bir sıra addımlar icra edirik. Nümunə olaraq evdən işləmək üçün tapşırıq sürücüsündən istifadə edək. Atdığım addımlar əsasən aşağıdakılardır:

  1. Maşında otur
  2. Bir dostunun evinə gedin, onlara gəzinti verin
  3. Çalışdığım ofisə aparın
  4. Maşınımı park qarajına qoyun

Bu işi başa çatdırmaq üçün yerinə yetirməyim lazım olan addımlar dəsti (alqoritm).

İndi eyni işi başa çatdırmaq üçün atdığınız lazımi addımlar barədə düşünün. Çox güman ki, onların məndən bir qədər fərqlidir. Alqoritmlərimiz fərqli ola bilər, amma məqsədimiz eynidir.

Kompüter proqramları çox da fərqlənmir: bir sıra vəzifələri yerinə yetirmək üçün istifadə edilə bilən müxtəlif alqoritmlər mövcuddur. Tez-tez nə olduqları ilə özümüzü maraqlandırmırıq, sadəcə onlardan istifadə edirəm (özüm daxil edirəm).

Məsələn, Waze və Google Maps, iki yer arasındakı ən yaxşı marşrutu hesablayan alqoritm nə kimi görünməlidir? Netflix-in izlədikləriniz əsasında filmlər və seriallar təklif edən alqoritmi haqqında nə demək olar?

Şəxsən mən sizə deyə bilmədim. Ancaq mən səmərəli olduqlarını bilirəm. Səmərəlilik bir alqoritmin mürəkkəbliyini təhlil etmək üçün istifadə etdiyimiz standartdır.

Alqoritm mürəkkəbliyi nədir?

Kompüter elmində alqoritm mürəkkəbliyi bir alqoritmin giriş həcminə görə bir tapşırığı yerinə yetirmək üçün nə qədər vaxt və məkan sərf etməsinə aiddir.

Ümumiyyətlə, alqoritmlər həm vaxt, həm də məkan istehlakı ilə qiymətləndirilir, ancaq bu yazıda zamanın mürəkkəbliyinə toxunacağam.

Vaxtın mürəkkəbliyini təhlil etmək alqoritmin giriş elementlərinin artması nəzərə alınmaqla necə davranacağını müəyyən etməyə imkan verir. 10, 100 və ya 1000 elementi emal etmək vaxtı haqqında bir təsəvvürə sahib ola bilərik.

Və bu analiz nə üçün vacibdir?

  • Hansı alqoritmin ən səmərəli olduğunu müəyyən etmək;
  • Daha səmərəli alqoritmlər hazırlaya bilmək;
  • Bir alqoritm kitabxanasının və ya həqiqi dilinin səmərəli olub olmadığını təhlil edə bilmək.

Xülasə etmək üçün səmərəlilik məqamdır!

Zaman mürəkkəbliyi

Bir fəaliyyətin bağlanması üçün vaxt lazımdır.

Əsasən bir maşın göstərişinin sayını sayan Frequency Count metodu ilə vaxt analizinə başlaya bilərik. Hər addım (təlimat) 1-dən başlayaraq vaxt vahidi təyin olunur.

Alqoritmin sərf etdiyi vaxt f (n) funksiyası ilə ifadə olunur, burada n məlumat ölçüsünü təmsil edir.

Təhlilin nəticəsi aşağıdakı kimi ifadə edilir:

([vaxtı ifadə edən funksiya]) = [Vaxt vahidlərinin cəmi]

İndi bunun həqiqətdə necə işlədiyini başa düşmək üçün bəzi alqoritmləri təhlil edək.

Birinci funksiya iki tam ədəd əlavə edir:

Görə bilərik ki, deyilən tapşırıq üçün tətbiq olunan alqoritm yalnız bir addım yerinə yetirir: iki ədədin cəmlənməsi. Hər addım üçün bir dəyər verdiyimiz üçün nəticə f (n) = 1-dir.

Növbəti nümunəyə baxaq, bir tamı başqa bir tam ilə bölən bir alqoritm:

Xülasəyə bənzər bir riyazi əməliyyat olmasına baxmayaraq, alqoritm daha çox addımları özündə cəmləşdirir, çünki bölücünün 0 olub olmadığını yoxlamaq lazımdır; əgər belədirsə bölmə gerçəkləşməyəcəkdir. Cəmi dörd addım olduğumuzdan və bunların hər birinə 1 dəyər verildiyi üçün nəticə f (n) = 4dür.

Növbəti alqoritm tam say siyahısının bütün elementlərini cəmləşdirir:

Bu alqoritmdə addımlardan biri təkrarlama üçün bir təlimat daxildir; bu o deməkdir ki, içindəki kod bir neçə dəfə icra ediləcəkdir. Edamların sayı məlumatların ölçüsündən asılı olduğundan n dəyərini vaxt vahidi kimi qeyd edirik. Nəticə f (n) = 2n + 3.

Növbəti alqoritm bir siyahının cəminə ikinci siyahının cəmini əlavə edir.

Nəticədə f (n) = 2n² + 2n + 3 olur.

Bu vaxta qədər yalnız sadə alqoritmləri gördük, elə deyilmi? İndi daha mürəkkəb alqoritmləri təhlil etdiyinizi və bu hesablamaları aparmağa ehtiyacınız olduğunu düşünün? Çox mümkün deyil, elə deyilmi? Ən uyğun görünsə də, çox zəhmətkeşdir və günün sonunda buna dəyər deyil.

Ümumiyyətlə, bir alqoritmi təhlil edərkən, emal etmək üçün çox sayda element olduqda onun davranışlarını öyrənməyə çalışırıq. Bu vəziyyətlərdə vaxt vahidlərinin cəminin üstünlük müddətini tapmaq lazımdır.

Məsələn, üçüncü alqoritm cəminin üstünlük təşkil edən müddəti nədir?

f (n) = 2n + 3

Bu vəziyyətdə üstünlük təşkil edən müddət 2 * n, mən bunun səbəbini izah edəcəyəm!

N-nin 1 (n> 1) -dən böyük olduğu hər hansı bir vəziyyətdə məhsul (vurma nəticəsi) artıq məbləğin ikinci müddətindən artıq olacaqdır.

Bir şey sınayın: n-ni 1-dən çox olan hər hansı bir tam ədəd ilə əvəz edin və vurma funksiyasını yerinə yetirin.

Son alqoritm cəminin üstünlük təşkil edən müddəti haqqında nə demək olar?

f (n) = 2n² + 2n + 3

Bu vəziyyətdə üstünlük təşkil edən müddət 2 * n²-dir, çünki n> 1 olduqda məhsul həmişə cəmin ikinci və üçüncü şərtlərindən çox olacaqdır. Gedin, sınayın!

Ergo, sabit və daha az əhəmiyyətli şərtlərin nəzərə alınmadığı alqoritmlərin mürəkkəbliyini təhlil etmək üçün daha ümumi bir yol var. Bu üsul Asimptotik Mürəkkəblik adlanır.

Mürəkkəblik Sifarişinin Notation-O və ya Big-O adı ilə də tanındığı yer budur.

Big-O Notation

İşlənmiş elementlərin sayı böyüdükcə əməliyyatların böyümə sürətini nəzərə alaraq bir alqoritmi təsnif etmək üçün istifadə olunur.

Big-O notation eyni zamanda bir alqoritmin zaman mürəkkəbliyini ifadə edən bir funksiyanı təyin edir. Bu məqsədlə n hərfi O hərfinin funksiyası kimi istifadə olunur.

Ən çox yayılmış siniflər:

  • O (1) - Daimi, elementlərin sayı artdıqca əməliyyatların sayı artmır
  • O (log n) - Loqarifmik, əməliyyatların sayı elementlərin sayından azdır
  • O (n) - Xətti, əməliyyatların sayı elementlərin sayı ilə mütənasib olaraq artır
  • O (n²) kvadratikdir, əməliyyatların sayı elementlərin sayından çox olacaqdır
  • O (2 ^ n) - Exponencial, əməliyyatların sayı elementlərin sayı ilə müqayisədə sürətlə artır
  • O (n!) - Faktiki olaraq, az sayda element üçün belə, əməliyyatların sayı çox sürətlə artır

Aşağıda, Əməliyyatların böyümə nisbətini x Elementlərin sayı nisbətini göstərən bir qrafik var.

Qrafik aşağıdakı kimi təsnif edilir:

  • Qırmızı zona dəhşətlidir, çəkinin!
  • Portağal zonası pisdir, bundan da çəkinin!
  • Sarı zona ədalətli, məqbuldur!
  • Açıq-yaşıl zona yaxşıdır, sərin!
  • Tünd-yaşıl zona əladır, təbriklər!

İndi biz əvvəllər bəhs olunan alqoritmləri təsnif etmək üçün Big-O notation-dan istifadə edəcəyik, həmişə üstünlük təşkil edən terminləri bizi istiqamətləndirmək üçün istifadə edirik.

İlk alqoritm f (n) = 1 ilə nəticələndi; o deməkdir ki, elementlərin artmasından asılı olmayaraq alqoritm yalnız bir əməliyyatı yerinə yetirir. Beləliklə, alqoritmi sabit - O (1) olaraq təsnif edə bilərik.

İkinci alqoritm f (n) = 4 ilə nəticələndi; o deməkdir ki, elementlərin artmasından asılı olmayaraq alqoritm dörd əməliyyatı yerinə yetirəcəkdir. Beləliklə, biz də bu alqoritmi sabit - O (1) olaraq təsnif edə bilərik.

Üçüncü alqoritmin nəticəsi f (n) = 2n + 3; n bu funksiyada dəyişən kimi xidmət etdiyini görərək əməliyyatların sayının elementlərin sayı ilə mütənasib şəkildə artacağını bildirir. Beləliklə, bu alqoritmi Xətti - O (n) olaraq təyin edə bilərik.

Son alqoritmin nəticəsi f (n) = 2n² + 2n + 3 ilə nəticələndi, yəni əməliyyatların sayı elementlərin sayından çox artacaqdır. Bu vəziyyətdə n də dəyişkən olaraq xidmət edir, ancaq ikinci gücə (kvadrat) qaldırılır. Beləliklə, bu alqoritmi Kvadrat - O (n²) olaraq təyin edə bilərik.

Aşağıdakı cədvəl elementlərin sayının böyüməsinə aid olduğu üçün əməliyyat sayının artımını göstərir.

Diqqət yetirin, bir eksponent alqoritmdə 16 element ən azı 65.5536 əməliyyatla nəticələnəcəkdir. Çox narahat, doğrudanmı?

Ümumiyyətlə, analiz prosesi etdiyimizlə eynidir: addımların sayını və üstünlük təşkil edən müddəti müəyyənləşdirmək.

Müşahidə edə biləcəyimiz bəzi meyllər:

  • Təkrarlama döngəsi olmayan alqoritmlər sabit olmağa meyllidir - O (1)
  • Təkrarlanma döngələri olan alqoritmlər, yuva altına alınmadığı müddətcə Xətti olmağa meyllidirlər - O (n)
  • İki yuvalı təkrarlama döngəsi olan alqoritmlər Kvadrat olmağa meyllidir - O (n²)
  • Bir sıra indeksinə birbaşa giriş ümumiyyətlə O (1) (sabit)
  • Siyahı uzatma metodları, orta hesabla, O (n) -dir. Məsələn: hər hansı, cəm və filtr.
  • Bubble Sort, Insertion Sort və Selection Sort kimi çeşidləmə alqoritmləri adətən O (n²) olur.

Alqoritmlərin necə təsnif olunacağını bilmək bizə bir alqoritmin səmərəliliyini və ya səmərəsizliyini mühakimə etmək imkanı verir. Əlbəttə ki, dəqiq işləmə müddətini saniyə, dəqiqə və ya saatda ölçə bilmirik. Bunun üçün yerinə yetirilməli, ölçülməli və dəyişdirilməlidir. Təsəvvür edin ki, çalışan alqoritmlər saatlarla, hətta günlərlə davam edir. Heç bir şans yoxdur!

Ümid edirəm bu yazının hədəfini yerinə yetirdim, bu da Alqoritmlər və Frekans Hesablama və Big-O metodlarından istifadə edərək təhlil etməkdir.

Aşağıdakı bəzi arayışları əlavə oxu materialı olaraq buraxdım!

İstinadlar:

Vídeos 1 ilə 1.7 arasında

Texnologiya vasitəsilə kredit bazarına yenilik gətirmək istəyirsiniz? Heyətimizə qoşulmaq üçün həmişə yeni insanlar axtarırıq!

Buradakı açılışlarımızı nəzərdən keçirin.