złozonosc nx: Witam mam taki algorytm: http://zapodaj.net/1045f56696be.jpg.html i mam za zadanie okreslic jego złozonosc obliczeniową i mam mały problem(od razu widac ze nie jest on efektywny ale mniejsza o to na razie) obliczyłem ze dla liczby a ktora jest nieparzysta wykonuje on stałą liczbę porowna wynoszącą 50 ale policzyłem tez(nie jestem pewien czy dobrze) ze dla a parzystego wykonuje on 2*a porównan i teraz(nie wiem czy dobrze mysle) że złozonosc obliczeniowa tego algorytmu będzie sumą liczby porownan dla a nieparzystego i dla a parzystego jesli tak to jak inaczej zapisac liczbe porownan dla a parzystego tzn uzaleznic ją od n

Trivial: Znasz notację asymptotyczną?

nx: znaczy z tym omikrone tzw O duze chyba

nx: asymptotyczna to jednak co innego widze to nie znam na razie przynajmniej

Trivial: Pierwsza część − inicjalizacja aż do i := 2 zabiera O(1) czasu.

	a
W najgorszym przypadku będziemy musieli wykonać O(a) porównań (tak naprawdę		, ale
	2

	1
		jest wciągnięta w notację 'O dużego'). Czyli....
	2

T(a) = O(1) + O(a) = O(a).

Trivial: Oj źle... O(a) jest dla liczby parzystej. Dla liczby nieparzystej zawsze 50.

Trivial: A tak na marginesie, przykład ten jest mało interesujący, bo kto potrzebuje określać złożoność obliczeniową, dla algorytmu, który obsługuje liczby z przedziału [0..100]. Zawsze zakończy się w ułamku sekundy.

nx: aha czyli bierzemy tu tez pod uwage sprawdzanie warunku czy a nalezy do <0,100> tak wiem że i tak szybko by sie zakonczył ale chciałem pocwiczyc no i wziąłem sobie taki przykład

Trivial: Poćwicz na nierekurencyjnym sortowaniu. Tam określenie złożoności ma sens.

nx: ok dzięki widze ze musze jednak jeszcze duzo zrobic podobnych zadan

nx: Dzięki za wskazówke