Ćwiczenia 12: Złożoność czasowa i pamięciowa

Piramida to ostrosłup, którego podstawa jest kwadratem, a boczne ściany to tójkąty równoboczne.
Zlecono Ci pomalowanie bocznych ścian piramidy.
Malując piramidę, możesz wziąć ze sobą wiaderko farby, które starcza na pomalowanie 1m² powierzchni, co trwa 1 minutę.
Zarówno wejście na wysokość \(h\) metrów, jak i zejście na dół, trwają po \(\frac{h}{2}\) minut.
Podstawa piramidy ma długość \(n\) metrów.
Podaj, jakiego rzędu jest czas potrzebny do pomalowania całej piramidy.
Jaka jest asymptotycznie energia potencjalna (wypełnionej) piramidy?
Jedziesz w ciemności samochodem. W odległości \(n\) metrów przed samochodem idzie pieszy.
Jak ilość światła, która dociera do oczu kierowcy zależy od \(n\)?
- Jeżeli pieszy nie ma odblasków, nie jest ciałem doskonale czarnym i równomiernie rozprasza padające na niego światło.
- Jeżeli pieszy ma (idealny) odblask, który padające na niego światło odbija dokładnie tam skąd ono pada
  (a kierowca ma reflektory w oczach).
Zastanówmy się, jaka energia jest potrzebna do napompowania koła rowerowego.
Dla ustalonej objętości dętki, jakiego rzędu jest ta energia w zależności od ciśnienia?
Ciśnienie powietrza jest takie, jak ciężar słupa powietrza naciskającego z góry.
Chcemy się wznieść na taką wysokość, na której ciśnienie powietrza nie przekracza p.
Jakiego rzędu jest to wysokość?
Sformułuj warunek określający, czy element wstawiany do drzewa ma być wstawiony do lewego, czy prawego
poddrzewa, tak aby kolejne elementy były wstawiane na kolejnych poziomach od lewej do prawej.
Dana jest implementacja funkcji sprawdz o treści:
```
 
      let sprawdz (a:int) =
        let n = ???
        in if a < n then -1 else if a = n then 0 else 1;;
 
```
W tej implementacji pod ??? została ukryta pewna liczba całkowita.
Napisz funkcje znajdz, która odwołując się do funkcji sprawdz, znajdzie tę liczbę całkowitą.
Podaj złożoność czasową i pamięciową rozwiązania.

Uwaga: Zakładamy, że typ int reprezentuje dowolne liczby całkowite.
W szczególności nie można zakładać, że typ int jest skończony i tym samym używać stałych takich jak max_int.
[CEOI 2003, uproszczone zadanie Hanoi]
Wiadomo (z EMD), że żeby przełożyć \(n\) krążków w łamigłówce ,,wieże Hanoi'' trzeba wykonać \(2^n-1\) ruchów.
Napisz procedurę hanoi: int list → int → int, która dla zadanej konfiguracji krążków oraz słupka, na
którym początkowo znajdują się wszystkie krążki wyznaczy minimalną liczbę ruchów potrzebnych do uzyskania danej konfiguracji.

Słupki są reprezentowane jako liczby całkowite od 1 do 3.
Konfiguracja to lista numerów słupków, na których mają się znaleźć krążki, w kolejności od największych krążków do najmniejszych.
[VIII OI, zadanie Łańcuch]
(Przynieść i pokazać chiński łańcuch.)
W jednym ruchu można zawsze zdjąć lub założyć pierwsze ogniwo łańcucha.
Ponadto, jeżeli zdjęte są ogniwa o numerach \(1, 2, \dots, k-2\), a ogniwo nr \(k-1\)
jest założone, to w jednym ruchu można zdjąć lub założyć ogniwo nr \(k\).
Początkowo wszystkie ogniwa łańcucha są założone.
Napisz procedurę, której wynikiem jest lista ruchów prowadzących do zdjęcia \(n\) ogniw łańcucha.
Oblicz złożoność czasową i pamięciową rozwiązania.

Informatyka MIMUW

Ćwiczenia 12: Złożoność czasowa i pamięciowa