StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think this algorithm has O(n log n) complexity (C++, DevStudio 2k5). Now, I don't know the details of how to analyse an algorithm to determine its complexity, so I have added some metric gathering information to the code. The code counts the number of tests done on the sequence of 1's and 0's for any given input (hopefully, I've not made a balls of the algorithm). We can compare the actual number of tests against the O value and see if there's a correlation.</p> <pre><code>#include <iostream> using namespace std; bool HasEvenBits (string &sequence, int &num_compares) { bool has_even_bits = false; num_compares = 0; for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i) { for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j) { ++num_compares; if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1') { has_even_bits = true; // we could 'break' here, but I want to know the worst case scenario so keep going to the end } } } return has_even_bits; } int main () { int count; string input = "111"; for (int i = 3 ; i < 32 ; ++i) { HasEvenBits (input, count); cout << i << ", " << count << endl; input += "0"; } } </code></pre> <p>This program outputs the number of tests for each string length up to 32 characters. Here's the results:</p> <pre><code> n Tests n log (n) ===================== 3 1 1.43 4 2 2.41 5 4 3.49 6 6 4.67 7 9 5.92 8 12 7.22 9 16 8.59 10 20 10.00 11 25 11.46 12 30 12.95 13 36 14.48 14 42 16.05 15 49 17.64 16 56 19.27 17 64 20.92 18 72 22.59 19 81 24.30 20 90 26.02 21 100 27.77 22 110 29.53 23 121 31.32 24 132 33.13 25 144 34.95 26 156 36.79 27 169 38.65 28 182 40.52 29 196 42.41 30 210 44.31 31 225 46.23 </code></pre> <p>I've added the 'n log n' values as well. Plot these using your graphing tool of choice to see a correlation between the two results. Does this analysis extend to all values of n? I don't know.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload