ALG4

64 Rozdział 3. Analiza sprawności algorytmów

3.4. Przykład 3: Wpadamy w pułapkę

Zadania z dwóch poprzednich przykładów charakteryzowała istotna cecha: czas wykonania programu nie zależał od wartości, jakie przybierała dana, lecz tylko od jej rozmiaru. Niestety nie zawsze tak jest! Takiemu właśnie przypadkowi poświęcone jest kolejne zadanie obliczeniowe. Jest to fragment większego programu. którego rola nie jest dla nas istotna w tym miejscu. Załóżmy, że otrzymujemy ten „wyrwany z kontekstu” fragment kodu i musimy się zająć jego analizą:

const N-1G; int t(NJ;

funkcja_ad_hoc() i

int k, i;

int suna=0; while (i<N)

{

while (j<-t[i]) (

s uma = suna-2;

3-3*i;

i^i+1;    II ta

I

)

Uprośćmy nieco problem zakładając, że:

•    najbardziej czasochłonne są instrukcje porównania, wszelkie inne ignorujemy zaś jako nie mające większego wpływu na czas wykonania programu.

•    zamiast pisać explicite t_c wprowadzimy pojęcie czasu jednostkowego wykonania instrukcji, oznaczając go przez 7.

Niestety jedno zasadnicze utrudnienie pozostanie aktualne: nie znamy zawartości tablicy, a zatem nie wiemy, ile razy wykona się wewnętrzna pętla while\ Popatrzmy, jak możemy sobie poradzimy w tym przypadku:

n

Wyszukiwarka

Podobne podstrony:
ALG4 54 Rozdział 3. Analiza sprawności algorytmów Tematyką tego rozdziału jest tzw. złożoność oblic
ALG0 70 Rozdział 3. Analiza sprawności algorytmów Przykład: SRL=xn-3x„.i+2 x„ -2=0 daje
ALG4 74 Rozdział 3. Analiza sprawności algorytmów • funkcja d(n) musi spełniać następującą własność
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
Alg0 60 Rozdział 3. Analiza sprawności algorytmów •    Znak graficzny 3 należy czyta
ALG2 52 Rozdział 3. Analiza sprawności algorytmów Rys. 3 -
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else    //element zost
ALG8 68 Rozdział 3. Analiza sprawności algorytmów3.6. Nowe zadanie: uprościć obliczenia! Nic sposób
ALG2 72 Rozdział 3. Analiza sprawności algorytmówn o) = i, i = A + O, A =    1. Po t
ALG6 76 Rozdział 3. Analiza sprawności algorytmów Analogicznie dla 2 otrzymamy: Vn > 1, A(n,2) =
ALG8 78___Rozdział 3 Analiza sprawności algorytmówZad. 3-4 Proszę rozwiązać następujące równanie
ALG
2 12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostsz
ALG3 Rozdział 3Analiza sprawności algorytmów Podstawowe kryteria pozwalające na wybór właściwego al
ALG8 58Rozdział 3. Analiza sprawności algorytmów konania programu zależy od danej wejściowej n? W l
ALG4 194 Rozdział 7. Algorytmy przeszukiwania •    powinna być tatwo obliczalna, tak
12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostszych
ET4 64 Rozdział 4. Turystyka jako sektor gospodarki Decyzje inwestycyjne mogą mieć charakter: •
ALG4 24 Rozdział 1. Zanim wystartujemy Aby zaradzić zaanonsowanym wyżej problemom, przyjęło się zwy

więcej podobnych podstron