x-kom hosting

[C++] Problem z oszacowaniem złożoności obliczeniowej programu

osemka
utworzono
utworzono (edytowane)

Witam!

Mam problem z oszacowaniem ile razy wykona się taki fragment kodu:
[code]
suma_max = -127 * rozmiar_tablicy * rozmiar_tablicy - 1;
licznik = 0;
liczba_obiegow = 0;
rozmiar_tablicy = 1000;

for (wysokosc_prostokata = 1; wysokosc_prostokata <= rozmiar_tablicy; wysokosc_prostokata++) //zmiana rozmiarów prostokąta
{
for (szerokosc_prostokata = 1; szerokosc_prostokata <= rozmiar_tablicy; szerokosc_prostokata++)
{
pozycja_pion = 0;
while (pozycja_pion + wysokosc_prostokata <= rozmiar_tablicy) //przesówanie prostokąta po tablicy
{
pozycja_poziom = 0;
while (pozycja_poziom + szerokosc_prostokata <= rozmiar_tablicy)
{
suma_biezaca = 0;
for (i = pozycja_pion; i < wysokosc_prostokata + pozycja_pion; i++) // sumowanie zawartości prostokąta
{
for (k = pozycja_poziom; k < szerokosc_prostokata + pozycja_poziom; k++)
{
suma_biezaca += dane[i][k];
if (suma_max < suma_biezaca) {suma_max = suma_biezaca;}
if (licznik >= 10000000000) //wskaźnik postępu ;)
{
liczba_obiegow++;
cout << "Program wykonal " << liczba_obiegow << " x 10 mld obiegow" << endl;
licznik = 0;
}
licznik++;
}
}
pozycja_poziom++;
}
pozycja_pion++;
}
}
}
[/code]

Sprzeczam się o to z kolegą od kilku dni. Mamy dwie różne koncepcje i jestem w kropce.

Czy mogę prosić o pomoc?

tessarac
komentarz
komentarz

Wg mnie najlepszą metodą na testowanie złożoności obliczeniowej programu jest obliczenie czasu, którego program potrzebuje na obliczenia. Chodzi mi o zastosowanie High Resolution Timerów.Przykład:
[code]long double ms;
unsigned __int64 freq, counterStart, counterStop;
QueryPerformanceFrequency(reinterpret_cast<LARGE_INTEGER*> (&freq));
QueryPerformanceCounter(reinterpret_cast<LARGE_INTEGER*> (&counterStart)); //rozpocznij pomiar czasu

//tutaj operacje programu
QueryPerformanceCounter(reinterpret_cast<LARGE_INTEGER*> (&counterStop)); //koniec pomiaru czasu
ms = (static_cast<long double> (counterStop) - counterStart) / freq * 1000; //wynik w ms, gdy mają być us -> freq * 1000000;
[/code]
Najlepiej puścić cały program w pętli i wziąć z tego średnią, ponieważ 1 uruchomienie to alokacja pamięci i inne operacje które wydłużają czas działania.
Pozdrawiam

rafalluz
komentarz
komentarz

Widzę sporo zagnieżdżonych pętli, każda mniej więcej do N - rozmiaru_tablicy, złożoność będzie wielomianowa, ale z niemałym wykładnikiem, O(N^6).

Wciąż szukasz rozwiązania problemu? Napisz teraz na forum!

Możesz zadać pytanie bez konieczności rejestracji - wystarczy, że wypełnisz formularz.

×
×
  • Dodaj nową pozycję...

Powiadomienie o plikach cookie

Strona wykorzystuje pliki cookies w celu prawidłowego świadczenia usług i wygody użytkowników. Warunki przechowywania i dostępu do plików cookies możesz zmienić w ustawieniach przeglądarki.