1. Przekształcamy dane wejściowe na macierz sąsiedztwa - tworzymy macierz n x n (nazwijmy ją A) i wypełniamy przy pomocy
tablic Pntr i EndVertex (skrypt Kubale, str. 86) (O(m))

2. Tworzymy drugą macierz (nazwijmy ją B) i wpisujemy do niej wynik podniesienia tej pierwotnej do kwadratu (naiwnym
algorytmem O(n^3)) //Mozna uzyc algorytmu strassena wtedy bedzie O(n^2,376)

3. Przeglądamy jednocześnie tablice A i B. Tam, gdzie w A znajdzie się 1, sprawdzamy co znajduje się B. Jeżeli liczba >= 2, to
robimy return true. Po dojściu do końca macierzy return false. (O(n^2))

(czyli sprawdzamy czy istnieją ścieżki z wierzchołka (i,j) długości 1 oraz dla tych samych wierzchołków muszą

istnieć 2 ścieżki długości 2)

by blue

Asymptotyczna liczba kroków to O(n) czyli złożoność obliczeniowa to
O(2^r) czyli wykładnicza a co do pierwszej częsci n<10 to z wzoru na
fibonnaciego mozna uznac ze O(2^n) Giaro str. 34 ale jak to blue
powiedzial mamy ograniczone przez 10 wiec to pomijamy

procedure odpowiedz

(

a

:

integer

)

begin
n

=

log

(

a

)

;

{n tym razem to romiar liczby (zazwyczaj jest r)}

if n<

10

then for i

:=

1

to n^

2

do

write

(

'Niech się święci pierwszy maja'

)

;

else for i

:=

1

to n

+

90

do

write

(

'Wiwat trzeci maj!'

)

;

end;

by Tom_vtec

procedure bucket

-

sort

(

A

[

1..

n

]

:

array

)

begin

for i

:=

1

to n do

B

[

n

*

podloga

(

A

[

i

])]

:=

A

[

i

]

;

for i

:=

0

to n

-

1

do

sortuj_przez_wstawianie

(

B

[

i

])

;

polacz listy B

[

0

]

to B

[

n

-

1

]

w dokladnie tej kolejnosci

end;

Należy doprowadzić nasz ciąg do ciągu z przedziału [0..1] co ma
złożoność O(n)
Następnie posortować algorytmem sortowania kubełkowego który ma
złożoność O(n^2)
Następnie zwrócic środkowy element ciągu