Algorithm

Salam deməli belə 1 sualım var oxuduğum kitabda f(n) = n^2 + 500 pis f(n) = n + 100n + 500 isə yaxşı nəticə sayılır bunu başa düşdüm məsələn n lərin yerinə müəyyən rəqəmlər qoymağnan bunu başa düşmək olar amma bu yaxşı variant deyil bunu başa düşmək üçün yəni hansının yaxşı hansının pis olduğunu başa düşmək üçün 1 riyazi isbat necə etmək olar ? təşəkkürlər

Sualı verdi: Mövla (18/06/2017)

Yadda saxlama

algorithm. Qısa keçid.

Verilmiş cavablar və yazılan şərhlər (1 cavab var)

ahmed

(22:19, 19/06/2017 ) #68848

Salam. Birinci alqoritmin mürəkkəbliyi f(n) = n^2 + 500 , ikinci alqoritminki isə f(n) = n + 100n + 500 şəklində ifadə olunub. İkincini fərqləndirmək üçün g(n) adlandıraq, g(n) = n + 100n + 500. Bu ifadələr verilmiş məsələni həll etmək üçün alqoritmin tələb etdiyi əməliyyatların sayın göstərir. Proqramlaşdırmada alqoritmlərin mürəkkəbliyini qiymətləndirmək üçün adətən böyük O simvolundan istifadə olunur. Birinci alqoritmin mürəkkəbliyi O(n^2), ikincisininki isə O(n) -dir. Bu artıq isbat deməkdir.

Niyə birinci pis hesab olunur?

Təsəvvür edin CPU -nun sürəti 1Ghz -dir. Yəni bir saniyədə 1 milyard əməliyyat. Məsələnin həlli -də 1 milyon addımdan ibarətdir. Bu zaman f(n) bunun üçün 1milyon * 1 milyon əməliyyat istəyəcək. Bu da 1000 milyard eliyir , yəni 1000 saniyyə vaxt lazım olacaq birinci alqorimt üçün. İkinci alqoritm isə məsələni 1 saniyəyə həll edəcək.

Böyük O simvolu və alqoritmlər barəsində daha ətraflı Kenneth H. Rosenin Discrete Mathematics and İts Applications kitabınının (seventh edition) 3-cü – Algorithms paraqrafının 2-ci bölməsindən The Growth of Functions məlumat əldə edə bilərsiniz.

Cavablamaq üçün sağ sütundan hesaba daxil olmaq lazımdır

Bu suala aid öz sualım var:
Sual verin

Bu suala cavab vermək istəyirəm:
Cavab verin