3 ms·
Yeah, it's polynomial, but it's still really slow and not practical. In a string of length N, there are N substrings of length 1, N-1 substrings of length 2, N
by scott_s 18y ago
Yeah, it's polynomial, but it's still really slow and not practical.
In a string of length N, there are N substrings of length 1, N-1 substrings of length 2, N-2 substring of length 3, ..., 1 substring of length N. This is the sum of the first N integers, which is N(N+1)/2. If we're doing big oh analysis, we can just say that's O(N^2).
Comparing every something to every other something is an N^2 operation. But, in this case, our something is already O(N^2), so the final algorithm is actually O(N^4).
Doing a O(N^4) algorithm on nontrivial sizes of N (and nontrivial sizes of N are where you need it the most) will take a long time.
Disclaimer: it's been a long time since I've done any algorithm analysis, so please check my work.
- ramchip 18y agoMy algorithms teacher does research in something similar. IIRC he has a program exactly for showing copy/pasted code. You may want to have a look at his papers on Clone Detection Tools, "A Novel Approach to Optimize Clone Refactoring Activity", etc. http://www.polymtl.ca/recherche/rc/en/professeurs/details.php?NoProf=123&showtab=PUB http://www.polymtl.ca/recherche/rc/en/professeurs/details.ph...
- silentbicycle 18y agoAwesome, thanks!
- lacker 18y agoComparing every something to every other something is an N^2 operation. But, in this case, our something is already O(N^2), so the final algorithm is actually O(N^4). If you are just checking for equality, comparing each of N items to another group of N items is O(N). Use a hash table.
- silentbicycle 18y agoExactly. Interned strings / symbols work out the same, too.