osemka utworzono 26 czerwca 2010 utworzono 26 czerwca 2010 (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 27 czerwca 2010 komentarz 27 czerwca 2010 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 27 czerwca 2010 komentarz 27 czerwca 2010 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.