dotnet-musahibe-suallari-toplusu--big-o-notation

.NET musahibə sualları toplusu: Big O Notation

Hansı proqramlaşdırma dilində yazmağımızdan asılı olmayaraq, iştirak etdiyimiz müsahibələrdə bütün suallar heç də konkret müsahibəyə dəvət edildiyimiz texnologiya və ya proqramlaşdırma dilindən ibarət olmur.

               İndiyə kimi özümün və tələbələrimin dəvət edildiyi müsahibələrə əsaslanaraq çox rahat deyə bilərəm ki, sizə bir çox şirkətlərdə mütləq şəkildə alqoritmlər və data strukturlar haqqında suallar verəcəklər.  


Alqoritm və data strukturlar proqramlaşdırmanın təməl əsasını təşkil edir. Bu elə bir spesifik sferadır ki, hansı proqramlaşdırma dilində yazmağınızdan asılı olmadan hər bir proqramçının bilməli olduğu fundamental məlumatları özündə saxlayır.

               Bu məqalədə sizə alqoritmlərin sürətinin ölçülməsi haqqında danışacağıq.

Alqoritmlər bildiyimiz kimi, sonlu nəticəni əldə etmək üçün ilkin verilənlər üzərində aparılan əməliyyatlar ardıcıllığından ibarətdir. Yəni qısacası, alqoritm bizi sonlu  nəticəyə aparan konkret addımlar(operation) ardıcıllığıdır.

               Yaxşı alqoritm ilk öncə Düzgün(correctness) olmalıdır. Alqoritm məsələnin düzgün həll üsulunu saxlamadığı müddətcə alqoritmin digər atributlarının heç bir əhəmiyyəti qalmır.

               Yaxşı alqoritmin ikinci atributu onun rahat başa düşülən(understandability/readability) olmasıdır. Yaxşı yazılan alqoritm mütləq şəkildə müşayiət olunma üçün açıq olmalıdır. Yəni elə formada yazılmalıdır ki, sonradan o alqoritmə sizin və ya sizdən sonra həmin kodlarla işləyənlərin onu anlaması, müşayiət etməsi, dəyişməsi asan olsun.

               Və bugunki mövzumuzu əhatə edəcək məsələ alqoritmin 3cu atributu ilə bağlıdır. Bu, alqoritmin genişlənə bilən olması, effektiv olmasıdır. (effectivness/ scalable) Big O notation alqoritmin effektivliyi bölməsində öyrənilir. Alqoritmin effektivliyi dedikdə, onun sürətinin ölçülməsi nəzərdə tutulur.

               Alqoritmin effektivliyi complexity theory(теория сложности/ çətinlik teoriyası) bölməsində nəzərdən keçirilir. Alqoritmin sürəti bir çox daxili və xarici faktorlardan asılıdır. Həmin faktorların bəzilərinə aşağıdakıları aid edə bilərik:

-Time(zaman)

-Space(memory/yaddaş)

-Others:

--Network

--Hardware(Sensor,Scanner,Printer etc)

--Graphics vəs.

Yuxarıdakı faktorlardan ən əsas Time və Space faktorları önəmli rol oynayırlar.

Space complexity-yə təsir edən səbəblər:

1)funksiyaların çağrılması

2)dəyişənlər

3)data strukturlar

 

Time complexity-yə təsir edən səbəblər:

1)Əməliyyatlar ( + * - /)

2)Dövr prosesləri (for,while)

3)müqayisələr( < > ==)

 

Bir çox alqoritmlər zamanda qazansalar yer(space)-də itirirlər, digərləri əksinə, yerdə(space) qazananda vaxtda itirirlər. Çox az alqoritmlər həm zamanda həm yerdə qazanmağımızı təmin edirlər.

 

Alqoritmin effektivliyini ölçən zaman aşağıdakı case-lər ortaya çıxır:

-Every case –alqoritmin hər icra halında

-Best case -ən yaxşı icra halında

-Average case –ortalama icra halı

-Worst case - ən pis halda

-Excepted case  vəs.

               Big O notation məhz alqoritmin Worst case(ən pis halda) halında effektivliyini ölçmək üçündür. Worst case- alqoritmin ən pis halda hansı sürətə malik olacağını ölçmək formasıdır.


    Bəs nəyə görə alqoritmlərin sürəti adi qaydada timer ilə ölçülmür?

-Sizin yazdığınız hər hansı bir alqoritmi timer ilə ölçsək, ozaman nisbi sürət almış oluruq. Bu o deməkdir ki, yazdığımız alqoritm A kompyuterində 0.5 saniyə, B kompyuterində 1.3 saniyədə icra oluna bilər. Bu zaman alqoritmin sürəti kompyuterin parametrlərinə bağlı olur. Əgər alqoritm CPU-dan asılı olaraq hesablama aparırsa, takt tezliyi sürətli olan kompyuterdə alqoritm sürətli işləyir, zəif kompyuterdə isə zəif. Bizə isə elə bir ölçü vahidi lazımdir ki, kompyuter hansı sürətdə olur olsun, hansı parametrlərə sahib olur olsun, alqoritmin mütləq(dəqiq) sürəti dəyişməsin. Yəni kənar faktorlardan asılı olmadan alqoritmin sürətini ölçəcək ölçü vahidi lazımdır. Bu ölçü vahidi olaraq Worst case(ən pis halda) halında alqoritmin hansı sürətə malik olacağını götürürük.  Big o asymptotic notation və ya sadəcə Big O Worst case halını hesablamaq üçün nəzərdə tutulub.

               Big O həmçinin alqoritmə ötürülən parametrlərin(arqument) sayından asılı olmadan onun effektivliyini müəyyən etməyə imkan verir!! Yəni istər alqoritmə 10 elementdən ibarət, istərsə də 10000 elementdən ibarət massiv ötürülsün, biz yenə də alqortimin dəqiq sürətini hesablaya bilirik və bu sürət parametrlərdən asılı olmadan eyni olur. Big O –nu təsvir etmək üçün böyük O hərfindən istifadə edilir.

               Alqoritmlərin müxtəlifliyindən, daxili strukturundan, məsələni həll etmə yollarından asılı olaraq bir sıra təməl Big O Rules(qaydalar) ortaya çıxır. Həmin qaydalar aşağıdakılardır:


1)     Əgər alqoritm məsələni həll etmək üçün ötürülən n elementlərdə gəzirsə(dövr edirsə)   ozaman f(N) üçün Big o notation O(f(N)) və ya sadəcə O(n)-ə bərabər olacaq.

    static bool IsFound(int[] inArray,int value)
        {
            bool _isFound = false;//O(1)

            foreach (int item in inArray)//O(n)
            {
                if(item == value)
                {
                    _isFound = true;
                    break;
                }
            }
            //konstantlar iqnor olunduguna gore BIg O-su O(N) olur.
            return _isFound;
        }

Misal: Bir çox proqramlaşdırma dillərində default olaraq verilən dil konstruksiyası olan Array-lərdə axtarış(Search), Əlavə etmə(İnsert) və Silmə əməliyyatları(Delete) O(n) olaraq qəbul olunur. Bu o deməkdir ki, bu əməliyyatları yerinə yetirmək üçün worst case halında n sayda addım atılır. Sadə bir misal yazaraq buna baxa bilərik. Təsəvvür edək ki, ədədlər massivimiz var və bu massivdə 45 ədədini axtarıb tapmaq lazımdır. Ədəd ən yaxşı halda massivin ilk elementin da tapıla bilər, ən pis halda isə massivin sonuncu indeksində tapıla bilər. Baxmayaraq ki, dövr içərisində element tapıldıqdan sonra break qoyulub, yenə də bu əməliyyatın Big O-su O(n) ə bərabərdir. Çünki nəticə etibarilə Big O bizdə ən pis halı(worst case) hesablayır.


2)Əgər alqortim f(n) addım atırsa və eyni alqoritmdə g(n) addım atırsa ozaman alqoritmin Big O –su O(f(n)) + O(g(n))= 2n=n ə bərabərdir. Misalçün əgər bir funksiyamızın içərisində bir birinin içində olmamaq şərtilə dövr yazmışıqsa. Big O-da konstantlar ilə cəmlənmə və kontantlar ilə hasil zamanı konstantlar ixtisar olunduğuna görə 2n-i sadəcə O(n) olaraq qəbul edirik. Yazdığımız alqortimdə adətən 2 dövr prosesi olan zaman bu halla rastlaşırıq.


3)Alqoritmin hər bir f(n) elementi üçün g(n) sayda addım atılarsa ozaman bu alqoritmində Big O O(f(n)) * O(g(n)) = n * n = n2 bərabər olur. Adətən dövr içərisində dövr əməliyyatı yazdıqda bu case-i almaq olur.


4) 2ci bəndə uyğun olaraq f(n) addım atılarsa və  eyni alqoritmdə g(n) addım atılarsa, f(n) ilə g(n) arasında ölçü fərqi yaranarsa ozaman sadələşdirmə üçün g(n) addım ixtisar edilir və f(n)>g(n) üçün Big O O(n) ə bərabər qəbul edilir. Çünki biz alqoritmin ən pis halda işləməsini hesablayırıqsa ozaman ötürülən parametrlər nəqədər böyük olarsa f(n) ilə g(n) arasındakı nisbət fərqi də bir oqədər böyüyür və müəyyən vaxtdan sonra g(n) addımı hesablamayacaq dərəcədə kiçik formaya düşür və bununla da sadəcə f(n) addımlar nəzərə alınır.


5) Konstantlar iqnor olunur.

O(C * f(n)) = O(f(n))

O(f(C * N)) = O(f(N))

C+f(N) = f(N)

Tural

Tural Süleymani

Süleymani Tural Microsoft-un MCSD statuslu mütəxəssisidir, 2008-ci ildən bu yana proqramlaşdırma üzrə tədris aparır

Müəllifin bu dildə ən son postları

Bu yazıları da bəyənə bilərsiniz