Algorytmy i struktury danych - wymagania do sprawozdań

Back

1. Opisywanie przyjętych w programie założeń, jeśli nie jest to ogólnie przyjęte, np. jakie zostały wybrane przyrosty w metodzie shella (algorytmy sortowania), w jaki sposób usuwany jest element (algorytmy grafowe), itp.
2. Opisywanie złożoności algorytmów, operacji (notacja O) zamiast opisywania: "ten algorytm działa szybciej od tego", "ta operacja działa niespodziewanie szybko" itp. Należy wyjaśnić co wpływa na to, że algorytm wykonuje się w czasie np. O(nlogn). Dla algorytmów sortowania podać z którym zestawem danych wejściowych algorytm radzi sobie najlepiej, a z ktorym najgorzej (i uzasadnić).
3. Przeprowadzanie testów dla takiego samego zakresu danych wejściowych. Jeżeli np. trudno jest porównać czasy poszczególnych operacji na tym samym wykresie (czasy są bardzo małe dla jedengo algorytmu(struktury) a dla innego nieporównywalnie wielkie) to:
   • należy zastosować skalę logarytmiczną
   • a wszelkie inne rozwiązania dobrze uzasadnić
4. Wygładzenie wyników na wykresie, tak aby nie było dziwnych niewytłumaczalnych skoków poprzez:
   • kilkakrotne przeprowadzanie testów dla różnych danych wejściowych, aby wynik nie był zależny np. od konkretnego zestawu danych
   • jeśli czasy działania dla pojedynczych testów bardzo odbiegają od innych, można je odrzucić, a wyniki pozostałych testów uśrednić
   • wyznaczyć odchylenie standardowe (miara zmienności w zbiorze) , gdzie μ jest to średnia np. czasu działania, x_i to kolejne wyniki testów, a N liczba przeprowadzonych testów