Mövzu üzrə bənzər suallara da baxa bilərsiniz.

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


Kateqoriya: Sual . . Qısa keçid.

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

(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

Cavab verin


Cavab yazmaq üçün lütfən sağ sütundan və ya buradan hesaba daxil olun.

Üzvlər üçün giriş

Qeydiyyat

Elan qutusu

Software Developer - 571 xal

E. Hacı - 568 xal

Onar Alili - 526 xal

Dilsuz - 448 xal

Cabbarov Sübhan - 414 xal

Ruslan Butdayev - 328 xal

Namiq Bəndəli - 297 xal

U.Tarlan - 244 xal

Meherremoff - 234 xal

Bextiyar Azeroglu - 215 xal

Sistemə daxil olmuş 18674 sualdan 94%-dən çoxu cavablandırılmışdır.

Proyekt haqqında

E-Haci.net istehsalı. © 2010-2017