ASD ITN k1 05 2002 1

•f-Ł t ~

Zad.l Uporządkuj następujące funkcje ze względu na ich rosnący rząd wielkości: fi(n)= 3n*sin(n²), f₂(n)= lg(n²), f₃(n)= 3n+ lg(n!), f₄(n)= 100n+ 2 ^3lgn, f₅(n)= 0.01*n² + lg n⁴

Zisy-A    ocitgł.)    -ticHfłi³    jk ^ ^{+ <}V^V'

Zad.l Niech n oznacza zmienną przebiegającą liczby naturalne. Oceń prawdziwość każdej z ^ podanych zależności ^2^lgn=0(n)    (jrawdaj^ fałsz^

f    2²ⁿ = 0(2ⁿ)    prawda / Cfałsz,

i=

[z-    ftj.

Zad.l Uporządkuj następujące funkcje ze względu na ich rosnący rząd wielkości: fi(n)= n^f/2+lg(n), f₂(n)= Ig(n²), f₃(n)= 2 ^lg(n), f₄(n)= n²(n+n^2/3 )^m, f₅(n)= lg (n!) +(2 lg n)*n² + L^Y\ 2.    -V\    fu

Zad.l Przy każdym z ciągów zaznacz, czy jest (zaznaczamy TAK) czy nie jest (zaznaczamy NIE) uporządkowany rosnąco, ze względu na rząd występujących w nim funkcji (ne N) •W lg(n²), sin2n+Vn , 2^lgT- vt    <JAKj/ NIE

" ⁱ 1 OOOOn ^1/3 +n^l/2, lg n, 0.001 *n³ +6 TAK /(ME> n²lgn, n^3/2 lgn, lg³n    TAK l(NIlT

Zad. 2 Niech A będzie algorytmem, ktorego złożoność wyraża się funkcją n². gdzie n jest 6^ s rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze 100 Qo Ozj y (na pewmym komputerze) wynosi 1 sek. Oblicz, jaki jest maksymalny rozmiar zadania, które można rozwiązać przy pomocy tego algorytmu ( na tym samym komputerze) w ciągu lh ?

/ .

Zad. 2 Niech A będzie algorytmem, ktorego złożoność wyraża się funkcją rr. gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze 60    .]

(na pewnym komputerze) wynosi 9 sek. Oblicz, jaki jest maksymalny rozmiar zadania, które można rozwiązać przy pomocy tego algorytmu w ciągu 20h ?

Zad. 2 Niech A będzie algorytmem, którego złożoność wyraża się funkcją lg(n+4). gdzie n jest rozmiarem zadania. Czas wykonania tego algorytmu dla pewnego problemu o rozmiarze

Wyszukiwarka

Podobne podstrony:
ASD ITN k1 05 2002 2 które można rozwiązać przy pomocy tego algorytmu w ciągu lmin ? Ł Zad. 2 Nie
ASD ITN k1 05 2002 4 z) wykona on rzędu 0(lg(nn)) porównań Zad. 6 Niech SPLIT będzie algorytmem roz
ASD ITN k1 05 2002 5 Zad. 8 Ile przestawień elementów wykona algorytm inserion-sort (sortowania prz
ASD ITN k1 05 2002 6 - f Zad 9. Przy każdej z wymienionych zależności dotyczących programu P, zazna
ASD ITN e! 06 2002 C 1 Algorytmy i Struktury Danych Egzamin ITN 2002-06*21 grupa C Proszę uważnie pr
ASD ITN k1 05 2002 3 ^VArcT ^ ckw^^/wKClu^(Lx-C t/oi irq ^ItyLoUtcłu<./
rozbójnik lab (2) IEF-DI Algorytmy i struktury danych laboratorium zaliczenie poprawkowe całości I.

więcej podobnych podstron