This week is the week for us to learn the proof methods, and we finished the method ‘proof by cases’. And then professor introduced the concept of counting steps, which includes the worst case and the best case. Let us talk about proof by cases firstly.
Sometimes we have to prove some claims that have conclusive antecedents. For example, if we now have a claim with an antecedent like this: | x - y | = e, we have to consider it by cases, for we know few ways to prove directly by absolute value. So we split | x - y | = e into two cases:
x - y = e and | x - y | = -e. Then we prove in this structure:
Case 1： x - y = e
......
Case 2： x - y = -e
......
Then we have a lot of ways to figure out the claim, since we are familiar to the equation
x - y = e and x - y = -e, and we know plenty of ways to do transformation on them.
After that, we learned how to count steps. It is a tough part because we need to be careful or we will easily go on a wrong way. Counting the worst case is the most representative case of counting steps because it includes all the possibilities. Worst case is the situation that the algorithm has to run the largest times that it can run. For example, the worst case ①of the algorithm
def LS(A, x):
’’’
Return index i, x == A[i].
Otherwise, return -1
’’’
i = 0 ①
while i < len(A): ②
if A[i] == x: ③
return i
i = i + 1 ④
return -1 ⑤
If it is in the worst case:
It has to run once at step ①, twice at step ②, once at step ③, once at step ④, and once at step ⑤ if len(A) = 1.
It has to run once at step ①, three times at step ②, twice at step ③, twice at step ④, and once at step ⑤ if len(A) = 2.
It has to run once at step ①, four times at step ②, three times at step ③, three times at step ④, and once at step ⑤ if len(A) = 3.
......
So when len(A) = n, it has to run 1+( n + 1) + n + n +1 = 3n + 3 times.
Next week we are supposed to enter a new world of logic. Although until now I have no idea about how that world is, I cannot be more excited on exploring it!
没有评论:
发表评论