(2017-06-19 22:19:58)
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.
Verilmiş nöqtənin hansı qapalı sahədə yerləşdiyini necə təyin etmək olar?