|
Алгоритмдер және деректер құрылымы Дәріс №1
|
| Дата | 28.04.2023 | | өлшемі | 283,44 Kb. | | #88132 | | түрі | Лекция |
| Байланысты: Лекция №1 Лекция №1 Алгоритмді талдау - Үлкен О
- Алгоритмді бағалау мысалдары: көпіршікті сұрыптау, енгізу сұрыптауы, екілік іздеу, біріктіру сұрыптауы.
Алгоритмді талдау
№ 1 Мысал Компьютер секундына 1млн стандартты операцияларды орындай алады. Осы компьютерді пайдалану арқылы келесі мәселелерді шешеміз: 1. бір миллиард (10млн) бүтін сандарды енгізу; 2. осы сандарды сұрыптаңыз. №2 Мысал * Енгізілген санды жай санға тексеру Алгоритмдерді талдау функциялары * Big Oh Анықтама 1. f(n) және g(n) - натурал сандарды қабылдайтын, оң нақты мәніндегі функциялар болсын. Сонда: f (n) = O (g (n)) немесе f = O (g) деп жазамыз, Егер барлық n натурал сандары үшін f (n) ≤ Cg(n) n ≥ N шарттары орындалатын C және N оң тұрақты сандар табылатын болса. Big O белгісі * Осы анықтамадан О-белгісі функцияның жоғарғы асимптотикасы екендігін көруге болады. Мысалдар * Келесі формулаларды дәлелде Мысалдар * Келесі формулалар дұрыс па? Алгоритмдерді талдау №1 Есеп. Массивті оқу Алгоритмдерді талдау №2 Есеп. Матрицаны оқу Алгоритмдерді талдау №3 Есеп. Масивті көпіршік әдісімен сұрыптау Алгоритмдерді талдау №4 Есеп. Алгоритмдерді талдау №5 Есеп. Жай санға тексеру
Достарыңызбен бөлісу: |
|
|
