Alqoritmin mürəkkəbliyi

Salam! Bugünkü mühazirə digərlərindən bir az fərqli olacaq. O, yalnız dolayı yolla Java ilə əlaqəli olması ilə fərqlənəcək. Ancaq bu mövzu hər bir proqramçı üçün çox vacibdir. Alqoritmlər haqqında danışacağıq . Alqoritm nədir? Sadə dillə desək, bu, istənilən nəticəni əldə etmək üçün yerinə yetirilməli olan müəyyən hərəkətlər ardıcıllığıdır . Gündəlik həyatda alqoritmlərdən tez-tez istifadə edirik. Məsələn, hər səhər bir vəzifə ilə qarşılaşırsınız: məktəbə və ya işə gəlmək və eyni zamanda:

• Geyinmiş
• Təmiz
• Yaxşı qidalanmış

Hansı alqoritm bu nəticəni əldə etməyə imkan verəcək?

1. Zəngli saata oyan.
2. Duş qəbul edin, üzünüzü yuyun.
3. Səhər yeməyi hazırlayın, qəhvə/çay dəmləyin.
4. Yemək.
5. Əgər axşamdan bəri paltarlarınızı ütüləməmisinizsə, onları ütüləyin.
6. Geyinmək.
7. Evi tərk et.

Bu hərəkətlər ardıcıllığı mütləq istədiyiniz nəticəni əldə etməyə imkan verəcəkdir. Proqramlaşdırmada işimizin əsas məqsədi daim problemləri həll etməkdir. Bu tapşırıqların əhəmiyyətli bir hissəsi artıq məlum olan alqoritmlərdən istifadə etməklə yerinə yetirilə bilər. Məsələn, bir vəzifə ilə qarşılaşırsınız: massivdə 100 addan ibarət siyahısını çeşidləyin . Bu problem olduqca sadədir, lakin müxtəlif yollarla həll edilə bilər. Burada bir həll var: Adların əlifba sırası ilə çeşidlənməsi alqoritmi:

1. İnternetdə "Rus Şəxsi Adlar Lüğəti" 1966-cı il nəşrini satın alın və ya yükləyin.
2. Siyahımızdakı bütün adı bu lüğətdə tapın.
3. Adın lüğətin hansı səhifəsində olduğunu bir kağız parçasına yazın.
4. Kağızdakı qeydlərdən istifadə edərək adları sıra ilə qoyun.

Belə bir hərəkət ardıcıllığı problemimizi həll etməyə imkan verəcəkmi? Bəli, buna tamamilə icazə verəcəkdir. Bu həll effektiv olacaqmı ? Çətinliklə. Burada alqoritmlərin başqa bir çox vacib xüsusiyyətinə - onların səmərəliliyinə gəlirik . Problem müxtəlif yollarla həll edilə bilər. Amma həm proqramlaşdırmada, həm də gündəlik həyatda ən təsirli olacaq metodu seçirik. Əgər vəzifəniz kərə yağı ilə sendviç hazırlamaqdırsa, əlbəttə ki, buğda əkməklə və inək sağmaqla başlaya bilərsiniz. Ancaq bu, təsirsiz bir həll olacaq - bu, çox vaxt aparacaq və çox pula başa gələcək. Sadə probleminizi həll etmək üçün sadəcə çörək və yağ ala bilərsiniz. Və buğda və inək ilə alqoritm, problemi həll etməyə imkan versə də, praktikada tətbiq etmək üçün çox mürəkkəbdir. Proqramlaşdırmada alqoritmlərin mürəkkəbliyini qiymətləndirmək üçün Big-O (“böyük O”) adlı xüsusi qeyd yaradıldı . Big-O, alqoritmin icra müddətinin ona ötürülən məlumatdan nə qədər asılı olduğunu təxmin etməyə imkan verir . Ən sadə nümunəyə baxaq - məlumat ötürülməsi. Təsəvvür edin ki, bəzi məlumatları fayl şəklində uzun məsafəyə (məsələn, 5000 kilometr) ötürmək lazımdır. Hansı alqoritm ən səmərəli olacaq? Bu, onun işləməli olduğu məlumatlardan asılıdır. Məsələn, bizdə 10 meqabaytlıq audio fayl var. Bu halda, ən səmərəli alqoritm faylı İnternet üzərindən ötürmək olardı. Yalnız bir neçə dəqiqə çəkəcək! Beləliklə, alqoritmimizi bir daha səsləndirək: "Əgər sizə 5000 kilometr məsafədə fayl şəklində məlumat ötürmək lazımdırsa, İnternet üzərindən məlumat ötürülməsindən istifadə etməlisiniz." Əla. İndi onu təhlil edək. Problemimizi həll edirmi? Ümumiyyətlə, bəli, tamamilə həll edir. Bəs onun mürəkkəbliyi haqqında nə deyə bilərsiniz? Hmm, indi işlərin maraqlı olduğu yer budur. Fakt budur ki, alqoritmimiz daxil olan məlumatlardan, yəni faylların ölçüsündən çox asılıdır. İndi 10 meqabaytımız var və hər şey yaxşıdır. 500 meqabayt köçürməli olsaq nə etməli? 20 gigabayt? 500 terabayt? 30 petabayt? Alqoritmimiz işləməyini dayandıracaqmı? Xeyr, bütün bu məbləğlər hələ də ötürülə bilər. Tamamlanması daha uzun sürəcək? Bəli, olacaq! İndi biz alqoritmimizin vacib bir xüsusiyyətini bilirik: ötürüləcək məlumatın ölçüsü nə qədər böyükdürsə, alqoritmin tamamlanması bir o qədər çox vaxt aparacaq . Amma biz bu əlaqənin nəyə bənzədiyini daha dəqiq başa düşmək istərdik (məlumatların ölçüsü ilə onu ötürmək üçün lazım olan vaxt arasında). Bizim vəziyyətimizdə alqoritmin mürəkkəbliyi xətti olacaqdır. “Xətti” o deməkdir ki, məlumatların həcmi artdıqca onun ötürülmə vaxtı təxminən mütənasib olaraq artacaq. 2 dəfə çox məlumat varsa və onu ötürmək üçün 2 dəfə çox vaxt lazımdır. 10 dəfə çox məlumat varsa, ötürmə müddəti 10 dəfə artacaq. Big-O notasiyasından istifadə edərək, alqoritmimizin mürəkkəbliyi O(N) kimi müəyyən edilir . Bu qeyd gələcək istinad üçün ən yaxşı şəkildə yadda saxlanılır; həmişə xətti mürəkkəbliyi olan alqoritmlər üçün istifadə olunur. Diqqət yetirin: burada ümumiyyətlə müxtəlif "dəyişən" şeylərdən danışmırıq: İnternet sürəti, kompüterimizin gücü və s. Alqoritmin mürəkkəbliyini qiymətləndirərkən, bunun sadəcə mənası yoxdur - onsuz da bizim ona nəzarətimiz yoxdur. Big-O, işləməli olduğu "mühitdən" asılı olmayaraq alqoritmin özünü qiymətləndirir. Nümunəmizlə davam edək. Deyək ki, sonda məlum olur ki, ötürüləcək faylların ölçüsü 800 terabaytdır. Onları internet üzərindən ötürsək, təbii ki, problem öz həllini tapacaq. Sadəcə bir problem var: çoxumuzun evlərimizdə istifadə etdiyi standart müasir keçid (saniyədə 100 meqabit) vasitəsilə ötürmə təxminən 708 gün çəkəcək. Demək olar ki, 2 il! :O Beləliklə, alqoritmimiz burada uyğun deyil. Bizə başqa bir həll lazımdır! Birdən IT nəhəngi Amazon köməyimizə gəlir! Onun Amazon Snowmobile xidməti sizə böyük həcmdə məlumatı mobil saxlama vahidlərinə yükləməyə və onları yük maşını ilə istədiyiniz ünvana çatdırmağa imkan verir! Beləliklə, yeni bir alqoritmimiz var! “Əgər 5000 kilometr məsafəyə fayl şəklində məlumat ötürmək lazımdırsa və internet vasitəsilə ötürüldükdə proses 14 gündən çox çəkəcəksə, Amazon yük maşını nəqliyyatından istifadə etməlisiniz.” 14 gün rəqəmi burada təsadüfi seçilmişdir: tutaq ki, bu, bizim ödəyə biləcəyimiz maksimum müddətdir. Alqoritmimizi təhlil edək. Bəs sürət? Yük maşını cəmi 50 km/saat sürətlə getsə belə, cəmi 100 saat ərzində 5000 kilometr qət edəcək. Bu, dörd gündən bir qədər çoxdur! Bu, İnternet ötürmə variantından daha yaxşıdır. Bu alqoritmin mürəkkəbliyi haqqında nə demək olar? O (N) də xətti olacaqmı? Xeyr, olmayacaq. Axı, yük maşını onu nə qədər yükləməyinizə əhəmiyyət vermir - o, hələ də təxminən eyni sürətlə sürəcək və vaxtında çatacaq. İstər 800 terabayt, istərsə də 10 dəfə çox məlumatımız olsun, yük maşını yenə də 5 günə çatacaq. Başqa sözlə, məlumatların yük maşını ilə çatdırılması alqoritmi daimi mürəkkəbliyə malikdir . “Sabit” o deməkdir ki, alqoritmə ötürülən məlumatdan asılı deyil. Yük maşınına 1GB fleşka qoyun və 5 günə gələcək. Oraya 800 terabayt məlumat olan diskləri qoyun və 5 günə gələcək. Big-O istifadə edərkən sabit mürəkkəblik O(1) kimi qeyd olunur . O(N) ilə tanış olduğumuzdan vəO(1) , indi daha çox “proqramçı” nümunələrinə baxaq :) Tutaq ki, sizə 100 nömrədən ibarət massiv verilib və tapşırıq onların hər birini konsola çap etməkdir. forBu tapşırığı yerinə yetirən müntəzəm bir döngə yazırsınız

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Yazılı alqoritmin mürəkkəbliyi nədir? Xətti, O(N). Proqramın yerinə yetirməli olduğu hərəkətlərin sayı ona tam olaraq neçə nömrənin ötürülməsindən asılıdır. Massivdə 100 ədəd varsa, 100 hərəkət (ekranda çıxış) olacaq.Massivdə 10.000 ədəd varsa, 10.000 hərəkətin yerinə yetirilməsi lazımdır. Alqoritmimizi təkmilləşdirmək olarmı? Yox. İstənilən halda, N-nin massivdən keçməsini və konsola N çıxışını yerinə yetirməli olacağıq . Başqa bir misala baxaq.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

LinkedListİçərisinə bəzi nömrələr daxil etdiyimiz boş nömrəmiz var . LinkedListNümunəmizə tək nömrə daxil etmək üçün alqoritmin mürəkkəbliyini və bunun siyahıdakı elementlərin sayından necə asılı olduğunu təxmin etməliyik . Cavab O(1) - sabit mürəkkəblikdir . Niyə? Diqqət edin: hər dəfə siyahının əvvəlinə nömrə daxil edirik. Bundan əlavə, xatırladığınız kimi, nömrələri elementlərə daxil edərkən , onlar heç bir yerə köçürülmür - bağlantılar yenidən müəyyən edilir (birdən LinkedList-in necə işlədiyini unutmusunuzsa, köhnə mühazirələrimizdənLinkedList birinə baxın ). Əgər indi siyahımızda birinci nömrə nömrədirsə və siyahının əvvəlinə y rəqəmini daxil ediriksə, lazım olan tək şey: х

x.previous  = y;
y.previous = null;
y.next = x;

Bu istinadın yenidən tərifi üçün indi neçə ədədin olması bizim üçün fərqi yoxdurLinkedList - ən azı bir, ən azı bir milyard. Alqoritmin mürəkkəbliyi sabit olacaq - O(1).

Loqarifmik mürəkkəblik

Təlaşlanmayın! :) Əgər “loqarifmik” sözü mühazirəni bağlamaq və daha sonra oxumamaq istəyi yaradırsa, bir neçə dəqiqə gözləyin. Burada heç bir riyazi çətinlik olmayacaq (başqa yerlərdə belə izahatlar çoxdur) və biz bütün nümunələri “barmaqlarda” təhlil edəcəyik. Təsəvvür edin ki, vəzifəniz 100 ədəddən ibarət massivdə müəyyən bir ədəd tapmaqdır. Daha doğrusu, ümumiyyətlə olub olmadığını yoxlayın. Tələb olunan nömrə tapılan kimi axtarış dayandırılmalı və konsolda “Tələb olunan nömrə tapıldı!” yazısı görünməlidir. Onun massivdəki indeksi = ....” Belə bir problemi necə həll edərdiniz? Burada həll yolu göz qabağındadır: birincidən (və ya sonuncudan) başlayaraq massiv elementlərini bir-bir təkrarlamaq və cari nömrənin istədiyinizlə üst-üstə düşməsini yoxlamaq lazımdır. Müvafiq olaraq, hərəkətlərin sayı birbaşa massivdəki elementlərin sayından asılıdır. Əgər 100 rəqəmimiz varsa, onda biz 100 dəfə növbəti elementə keçməliyik və 100 dəfə uyğunluq üçün nömrəni yoxlamalıyıq. Əgər 1000 ədəd varsa, onda 1000 yoxlama addımı olacaq.Bu, aydın şəkildə xətti mürəkkəblikdir, O(N) . İndi nümunəmizə bir aydınlıq əlavə edəcəyik: nömrə tapmaq üçün lazım olan massiv artan qaydada sıralanır . Bu, vəzifəmiz üçün nəyisə dəyişirmi? İstənilən nömrəni hələ də kobud güclə axtara bilərik. Ancaq bunun əvəzinə məşhur ikili axtarış alqoritmini istifadə edə bilərik . Şəklin yuxarı cərgəsində sıralanmış massiv görürük. Orada 23 rəqəmini tapmaq lazımdır. Rəqəmlər üzərində təkrarlamaq əvəzinə, sadəcə olaraq massivi 2 hissəyə bölüb massivdəki orta rəqəmi yoxlayırıq. 4-cü xanada olan nömrəni tapırıq və onu yoxlayırıq (şəkildə ikinci sıra). Bu rəqəm 16-dır, biz isə 23-ü axtarırıq. İndiki rəqəm azdır. Bu nə deməkdir? Bütün əvvəlki nömrələri (16-ya qədər olan) yoxlamağa ehtiyac yoxdur : onlar mütləq axtardığımızdan az olacaq, çünki massivimiz sıralanıb! Qalan 5 element arasında axtarışa davam edək. Diqqət edin:Biz yalnız bir yoxlama etdik, lakin mümkün variantların yarısını artıq aradan qaldırdıq. Cəmi 5 elementimiz qalıb. Addımımızı təkrarlayacağıq - qalan massivi yenidən 2-yə bölün və yenidən orta elementi götürün (şəkildə 3-cü sətir). Bu rəqəm 56-dır və axtardığımızdan daha böyükdür. Bu nə deməkdir? Daha 3 variantı - 56 rəqəminin özünü və ondan sonra iki rəqəmi (onlar mütləq 23-dən böyükdür, çünki massiv sıralanır) imtina edirik. Yoxlamaq üçün əlimizdə cəmi 2 nömrə qalıb (şəkildə sonuncu sıra) - 5 və 6 massiv indeksləri olan nömrələr. Biz onlardan birincisini yoxlayırıq və axtardığımız budur - 23 rəqəmi! Onun indeksi = 5! Gəlin alqoritmimizin nəticələrinə baxaq və sonra onun mürəkkəbliyini anlayacağıq. (Yeri gəlmişkən, indi bunun niyə ikili adlandığını başa düşürsünüz: onun mahiyyəti məlumatları daim 2-yə bölməkdir). Nəticə təsir edicidir! Xətti axtarışdan istifadə edərək istədiyiniz ədədi axtarsaydıq, 10 yoxlamaya ehtiyacımız olardı, lakin ikili axtarışla bunu 3-də etdik! Ən pis halda, onlardan 4-ü olardı, əgər son addımda bizə lazım olan nömrə birinci deyil, ikinci olsa idi. Bəs onun mürəkkəbliyi? Bu çox maraqlı məqamdır :) Binar axtarış alqoritmi xətti axtarış alqoritmi ilə müqayisədə (yəni sadə sadalama) massivdəki elementlərin sayından qat-qat az asılıdır. Massivdə 10 elementlə xətti axtarış üçün maksimum 10 yoxlama, ikili axtarış üçün isə maksimum 4 yoxlama tələb olunacaq. Fərq 2,5 dəfədir. Lakin 1000 elementdən ibarət massiv üçün xətti axtarışa 1000 yoxlama, ikili axtarışa isə cəmi 10 yoxlama lazımdır ! Fərq artıq 100 dəfədir! Diqqət edin:massivdəki elementlərin sayı 100 dəfə (10-dan 1000-ə qədər) artdı və ikili axtarış üçün zəruri yoxlamaların sayı cəmi 2,5 dəfə artdı - 4-dən 10-a. 10.000 elementə çatsaq, fərq daha da təsirli olur: 10.000 xətti axtarışı yoxlayır və ikili üçün cəmi 14 yoxlayır . Və yenə: elementlərin sayı 1000 dəfə artdı (10-dan 10000-ə), lakin çeklərin sayı cəmi 3,5 dəfə artdı (4-dən 14-ə). İkili axtarış alqoritminin mürəkkəbliyi loqarifmikdir və ya Big-O qeydində O(log n) olur . Niyə belə adlanır? Loqarifm eksponentasiyanın tərsidir. İkili loqarifm 2-nin gücünü hesablamaq üçün istifadə olunur. Məsələn, ikili axtarışdan istifadə edərək keçməli olduğumuz 10.000 elementimiz var. İndi gözünüzün qarşısında bir şəkil var və bunun üçün maksimum 14 yoxlama tələb olunduğunu bilirsiniz. Bəs gözünüzün qarşısında heç bir şəkil yoxdursa və lazımi yoxlamaların dəqiq sayını hesablamalısınızsa nə olacaq? Sadə bir suala cavab vermək kifayətdir: 2 rəqəmini hansı gücə qaldırmaq lazımdır ki, alınan nəticə >= yoxlanılan elementlərin sayı olsun? 10000 üçün 14-cü güc olacaq. 2-dən 13-cü dərəcə çox kiçikdir (8192) Amma 2-dən 14-cü dərəcəyə = 16384 , bu rəqəm bizim şərtimizi təmin edir (bu >= massivdəki elementlərin sayıdır). Loqarifmi tapdıq - 14. Bizə nə qədər çek lazımdır! :) Alqoritmlər və onların mürəkkəbliyi bir mühazirəyə daxil edilə bilməyəcək qədər geniş mövzudur. Ancaq bunu bilmək çox vacibdir: bir çox müsahibələrdə alqoritmik problemlər alacaqsınız. Nəzəriyyə üçün sizə bir neçə kitab tövsiyə edə bilərəm. Başlamaq üçün yaxşı yer " Grocking Alqoritmləri "dir: kitabdakı nümunələr Python dilində yazılsa da, kitabın dili və nümunələri çox sadədir. Başlayanlar üçün ən yaxşı seçimdir və həcmi də kiçikdir. Daha ciddi oxu: Robert Laforet və Robert Sedgwick -in kitabları . Hər ikisi Java-da yazılmışdır ki, bu da öyrənməni sizin üçün bir az asanlaşdıracaq. Axı siz bu dillə kifayət qədər tanışsınız! :) Yaxşı riyazi məlumatı olan tələbələr üçün ən yaxşı seçim Tomas Kormanın kitabı olardı . Ancaq yalnız nəzəriyyə ilə kifayətlənməyəcəksiniz! “Bilmək” != “bacarmaq” Siz HackerRank və Leetcode -da alqoritm məsələlərini həll etməyi məşq edə bilərsiniz . Oradakı problemlər hətta Google və Facebook-da müsahibələr zamanı da tez-tez istifadə olunur, buna görə də siz mütləq darıxmayacaqsınız :) Mühazirə materialını gücləndirmək üçün sizə YouTube-da Big-O haqqında əla video izləməyi məsləhət görürəm . Növbəti mühazirələrdə görüşənədək! :)