Programming time for algorithm? Anyone help me.................
-
I have coded the following: --------------------------------------------- //file BT01.h class BT01 { public: int BruteForce(char *P, char *T); void InputText(char *T, char *P); }; --------------------------------------------------- //file BT01.cpp #include "BT01.h" #include "time.h" #include "dos.h" #include <iostream> #include <conio.h> #include <stdio.h> using namespace std; int BT01::BruteForce(char *P, char *T) { //duyet T for (int i = 0; i <= strlen(T) - strlen(P); i++) { //khai bao j int j = 0; //duyet P while (j < strlen(P)) { //Kiem tra ptu tai T tai vi tri thu i + j co bang j hay khong? xu ly if (tolower(T[i + j]) == tolower(P[j])) j++; else break; } //Tim thay if (j == strlen(P)) return i; } //khong tim thay return -1; } void BT01::InputText(char *T, char *P) { do{ printf("T: "); gets(T); } while (strlen(T) < 1); do{ printf("P: "); gets(P); } while(strlen(P) < 1 || strlen(P) > strlen(T)); } void main() { char *P = new char[20]; char *T = new char[999]; printf("BAI TAP TH01 - THUAT TOAN BRUTEFORCE\n"); BT01 objBT01; objBT01.InputText(T, P); int kq; kq = objBT01.BruteForce(P, T); if (kq == -1) printf("KQ: Khong tim thay."); else printf("\nKQ: %i, %i", kq, strlen(T)); printf("\nThoi gian (ms): "); getch(); } I would like to count time for Algorithm BruteForce. How to count?
modified on Monday, December 22, 2008 11:00 PM
-
I have coded the following: --------------------------------------------- //file BT01.h class BT01 { public: int BruteForce(char *P, char *T); void InputText(char *T, char *P); }; --------------------------------------------------- //file BT01.cpp #include "BT01.h" #include "time.h" #include "dos.h" #include <iostream> #include <conio.h> #include <stdio.h> using namespace std; int BT01::BruteForce(char *P, char *T) { //duyet T for (int i = 0; i <= strlen(T) - strlen(P); i++) { //khai bao j int j = 0; //duyet P while (j < strlen(P)) { //Kiem tra ptu tai T tai vi tri thu i + j co bang j hay khong? xu ly if (tolower(T[i + j]) == tolower(P[j])) j++; else break; } //Tim thay if (j == strlen(P)) return i; } //khong tim thay return -1; } void BT01::InputText(char *T, char *P) { do{ printf("T: "); gets(T); } while (strlen(T) < 1); do{ printf("P: "); gets(P); } while(strlen(P) < 1 || strlen(P) > strlen(T)); } void main() { char *P = new char[20]; char *T = new char[999]; printf("BAI TAP TH01 - THUAT TOAN BRUTEFORCE\n"); BT01 objBT01; objBT01.InputText(T, P); int kq; kq = objBT01.BruteForce(P, T); if (kq == -1) printf("KQ: Khong tim thay."); else printf("\nKQ: %i, %i", kq, strlen(T)); printf("\nThoi gian (ms): "); getch(); } I would like to count time for Algorithm BruteForce. How to count?
modified on Monday, December 22, 2008 11:00 PM
I'm not sure what you mean by "count time". If you mean algorithmic complexity, the worst case running time would be O((T - P + 1) * P) because that's the maximum number of times the loops in BruteForce together can execute. A little calculus also shows that the worst occurs when P = (T + 1) / 2, in which case the running time would be O(T2). If you're looking to calculate the actual running time of the function, you should use a library function such as clock()[^] to get the time before and after calling the BruteForce function - then the difference in those times will give you the execution time.