Different Algorithm - How Does it Compare

Unreal Courses Talk
,
#1

I’m wondering how this algorithm compares (in terms of efficiency) to the method shown in the course which uses a map:

	for (int i = 0; i < strGuess.length(); i++) {
	int intCount = 0;
	for (int j = 0; j < strGuess.length(); j++) {
		if (strGuess[i] == strGuess[j]) {
			intCount++;
		}
	}
	if (intCount > 1) {
		guessStatus = EGuessStatus::Not_Isogram;
		break;
	}
}

It goes through each letter in the guess and compares it to all other letters in the guess; if a letter is seen more than once (i.e., ‘intCount’ > 1), then we break out of the outer loop and return the proper ‘error code’…

Bryan

#2

So the first time through the loop, you would have strGuess[0] compared to strGuess[0] since i and j both start at 0. that’s always going to give a match because it’s looking at the same character from the string, so you’ll get false positives every time.

Even if you fixed that to only fire when i and j are not equal, it’s inefficient:

Think about what would happen if the user entered “planee”. P would get compared to L, A, N, E, and E with no matches, so that’s 5 comparisons.

L would get compared to A, N, E, and E with no matches, so that’s 4 more comparisons.

A would get compared to N, E, and E with no matches, so that’s 3 more comparisons.

N would get compared to E and E with no matches, so that’s 2 more comparisons

It’s not until you get to the first E that you see the match with the second E, but that’s one more comparison

So in all the nested loops would run 15 comparisons to check a 6-letter word. The map version maxes out at 6 comparisons

#3

First thing I would make sure you’re declaring variables outside of loops and check if you want public, protected, or private. But that’s not really here nor there.

In terms of what was outline earlier, false positives will get you a lot.

Lastly, your algorithm, will be efficient to roughly N^2. While your size is relatively small, if we consider it in Big-O notation it is not efficient. And that’s not taking into account where this method is called. If you’re calling this method N times then it will get worse and go to N^3 efficiency.

Privacy & Terms