First, I'm going to use my favourite function as an example:
def string_together(x: 'list of str') -> str:
if len(x) == 2:
return x[0] + x[1]
else:
return string_together(y[:-1]) + y[-1]
Now, I want to analyze this mathematically. I'm going to assign variables for the amount of time that a computer will take to do a certain step:
X: Determining whether len(x) is 2. (call this 'step 1')
Y: Concatinating and returning x[0] + x[1]. (call this 'step 2')
Z: Concatenating and returning string_together(y[:-1]) + y[-1] (call this 'step 3')
Now, I do some arithmetic. To make notation easier, I'll name the initial length of x as n, and the total time taken as f(n). Lets require that n > 0 (only because of the way the function is written).
Lets say that len(x) is 2, the base case.
Then step 1 will be executed once, and step 2 will be executed once.
And so, the total time, f(2) is equal to X + Y.
Now, let len(x) be 3.
Step 1 will be executed, then step 3, and then there's a recursive call which will contain all of the steps in the above example (so, 1 and then 2).
Total time: f(3) = X +Z + X + Y = 2X + Y + Z
Now, let len(x) be 4.
Step 1 will be executed, then step 3, and then there's a recursive call which will contain all of the steps in the above example (1,3,1,2).
f(4) = X + Z + 2X + Y + Z = 3X + Y + 2Z
...
There's a pattern here. I generalize it as:
f(n) = (n-1)X + Y + (n-2)Z
And this is useful. For starters, if you want to find out the actual values of X, Y and Z, you can run a bunch of simulations, and do the linear regression (if you're into that sort of thing =p).
Question: When is f(n) large? (aka, when is the function slow)
Answer: f(n) is large when X, Y, Z, or n are large.
The thing is, I have some control over X, Y and Z. You know, because I've written my function to make them one line each. I don't expect them to vary a lot. I expect them to be small (but non-zero).
But n -- n could get as large as it wants.
New question: Can f(n) also get as large as it wants?
Answer: Yes. If you pick a number, I can choose an n big enough that f(n) will be greater than that number.
BUT, that said, there is a constraint on f. It's n. (and also X, Y and Z of course)
Question: So, what's a good way of expressing that f is constrained by n while still acknowledging that f is unbounded?
Answer: I can say that, given X, Y and Z,
I can pick some number C, and some easier-to-understand function g(n), such that no matter what number we try for n, it will always be true that C times g of n will be greater than f of n.
Or, for the mathematically inclined:
∃C∈ℝ: ∀n∈ ℕ\{1}, Cg(n) > f(n)
(Note that here, I proscribe n from taking non-integer values or values less than two)
(Gosh, this is ugly. I should learn LaTeX)
Anyways, to further simplify the notation, we say that the above is equivalent to the statement:
f is O(g(n)).
Let's return to the example.
f(n) = (n-1)X + Y + (n-2)Z
= (X + Z)n + (Y - X - 2Z)
So let g(n) = n, and let C = X + Z + |Y - X - 2Z | + 1.
Then
Cg(n) - f(n) = [(X + Z + |Y - X - 2Z + 1|)n] - [(X + Z)n + (Y - X - 2Z)]
= (|Y - X - 2Z | + 1)n - (Y - X - 2Z)
= (Y - X - 2Z + 1)n - (Y - X - 2Z) OR = (-Y + X + 2Z + 1)n - (Y - X - 2Z)
[Here, I split the problem based on whether Y - X - 2Z is positive or negative.]
= (Y - X - 2Z )(n - 1) + n || = (Y - X - 2Z)(1 - n) + n
> n [both factors are positive] || > n [both factors are negative]
> 0 || > 0
Therefore, Cg(n) > f(n) for all n; f is O(n).
That was fun.
The moral of the story: you only have to care about terms that make f larger as n gets larger.
And, though I haven't quite shown this: if there are more than one, you only have to care about the one the grows fastest with large n.
What about sorting a list, then? What do I know about sorting algorithms?
Well, sorting algorithms operate by comparing values to see which is larger, then moving them if appropriate.
Well, sorting algorithms operate by comparing values to see which is larger, then moving them if appropriate.
This moving actually complicates this problem, because there's a practical difference between sorting a list in place, and making a sorted copy, I'm going to ignore this here.
Further, a single algorithm, might take different times for different lists, given that more operations might be required. An easy way to think about this: an already-sorted list does not require any movement to be sorted.
I'm going to consider some possibilities...
What about some magical, ideal sorting algorithm? Well, it's going to have to do at least n - 1 comparisons -- just enough to check that an already-sorted list is sorted, by checking each element against the next one.
In the best case, it won't have do to any moving, because the list will already be sorted.
From this, we see that this magical, unfettered algorithm will take n -1 of these steps, and so will be O(n).
What about an equally contrived, magically-awful algorithm? Well, it shouldn't have to do any single comparison more than once. So, let's say it does all possible comparisons. That's (n - 1) for the first element, (n - 2) for the second, and so on. Overall, that's n(n - 1)/2.
In the worst case, each element will have to be moved individually to its spot -- except for the final one. In this case, you need n - 1 movements. Hm, maybe that's not bad enough, actually. Ok, how about every time you move one item, you have to move all the other unsorted items, too. Then this also takes n(n - 1)/2.
From this, this algorithm will take n(n-1) = n^2 - n of these steps, and so will be O(n^2).
So you see, without even considering any specific algorithms, we can expect all reasonably efficient algorithms to operate between O(n) and O(n^2). Further, these cases suggest that comparisons will generally be more important than the actual moving (not guaranteed).
[Author's note: please don't confuse my example of good//bad algorithms with the concept of best//worst cases for a single algorithm.]
Last question: I've done some reading on the subject, and O(nlog(n)) keeps coming up. Why?
Answer: Let's look at a real example.
Consider mergesort. For this algorithm, divide the list into two, recursively sort the halves, then combine the two in order. How many comparisons does it do? Approach this question the way you'd approach any question about the behaviour of a recursive function.
Base case: For n = 2, only one comparison is needed.
For n = 4, the group is split in half, then 1 comparison is done in each group, then 2-3 additional comparisons are required to merge them. (To merge, take the lowest element from each group, take the lowest of them as the lowest overall, and repeat. This can't take fewer comparisons than the number of items in a group, but it also can't require as many as the number of items in the two combined.) A total of 4-5 comparisons are required overall.
For n = 8, the group is split in half, and 4-5 comparisons are done in each half. Then merging takes 4-7 comparisons, for a total of 12-17.
...
In conclusion, the best cases take {1,4,12,...} and the worst cases take {1,5,17,...}.
I can describe these by functions which I'll call b(x) and w(x), for best and worst. I understand them best as they operate on powers of two, so that's how I'll write them. For N = 1,2,3,... :
Recursively:
b(2^N) = 2*b(2^(N - 1)) + 2^(N-1)
w(2^N) = 2*w(2^(N - 1)) + 2^(N) - 1
After some math:
Well, actually, I can't do the math. But look at the patterns:
b(2^N) gives {1, 1*2+2, 4*2 + 4, 12*2 + 8,...}
= {1*1, 2*2, 4*3, 8*4,...}
w(2^N) gives {1, 1*2 + 4 - 1, 5*2 + 8 - 1, 17*2 + 16 - 1,...}
= {2*0 + 1, 4*1 + 1, 8*2 + 1, 16*3 + 1,...}
--David
Which leads me to a conclusion:
b(2^N) = ((2^N)/2)*N
w(2^N) = (2^N)*(N - 1) + 1
Let n = 2^N. Then N = log(n). And:
b(n) = (n/2)*log(n) = (1/2)*nlog(n)
w(n) = n(log(n) - 1) + 1 = nlog(n) - n + 1
And so b(n) and w(n) are both O(nlog(n)). Tada!
[Author's note: an earlier version had 'O(n)' here. That was merely a clerical error, sorry for any confusion.]
But why???
[Author's note: an earlier version had 'O(n)' here. That was merely a clerical error, sorry for any confusion.]
But why???
In a nutshell, because log(n) is the time to find an item by binary search (this is because binary search eliminates half of all possibilities with each step, because doubling the number of elements to search will add only one more step, etc, etc), and n is the number of items to find. Mergesort doesn't quite have this cut-and-dry ~find one item, then find the next~ -style, but I'm now wondering if they aren't really very similar. But I'm fishing here. However I do know that the reasons are similar. Hmmm...
That's all for today, folks. I hope your midterms went well, and I hope you're not afraid of your finals.
Until next time, may you ask a bunch of questions, do the math and then ask more questions.
No comments:
Post a Comment