time complexity is just an partial part of measuring how good a program is.
why do time complexity useful? From my point of view, this is because we usually deal with a large amount manually-hard data by computer. when n becomes large enough, n*n is always larger than c*n no matter what constant c is.
computer or program's application of large and rigid characters make time complexity useful.
(1)Selection sort
It has O(n2) time complexity
def selection_sort(L):
"""Sort the items in L in non-decreasing order."""
i = 0
while i != len(L) - 1:
# Find the smallest remaining item and move it to index i.
smallest = min(L, i)
L[smallest], L[i] = L[i], L[smallest]
i += 1
the worst case is that always have to go through all the left items to get the minimum one.(i.e reversed-sorted one)
so n+(n-1)....+3+2+1= (n*n + n)/2
which is O(n2)
(2)Insertion sort
the time complexity is O(n)
every iteration this sort make sure the first k items (for kth iteration) is sorted.
so theworst case is that you need rearrange the total line in every iteration( i.e reversed-sorted one)
def insert(L, i):
"""Move L[i] to where it belongs in L[:i]"""
v = L[i]
while i > 0 and L[i - 1] > v:
L[i] = L[i - 1]
i -= 1
L[i] = v
def insertion_sort_1(L):
"""Sort the items in L in non-decreasing order."""
i = 1
# Insert each item i where it belongs in L[0:i + 1]
while i != len(L):
insert(L, i)
i += 1
(3) Bubblesort
Bubble sort has worst-case and average complexity both О(n2)
just like its mean, each iteration check all the items by comparing two adjoint items. If this two-pattern is unsorted, then switch, like bubling up.
From my point of view Bubblesort is worse than Selection sort although they are both O(n2) in the worst case.
def bubblesort_1(L):
"""Sort the items in L in non-decreasing order."""
j = len(L) - 1
while j != 0:
# Swap every item that is out of order.
for i in range(j):
if L[i] > L[i + 1]:
L[i], L[i + 1] = L[i + 1], L[i]
j -= 1
The reason that some may think it is better is because it do something useful for every comparison. But that is a illusion.
two steps a stage walking upstairs are faster than one steps a stage walking upstairs.
You can directly swith ith and jth item, but insteading of directing doing that, you switch the ith and i+1th first, then i+1th and i+2th...finally j-1th and jth.
It looks that you make some effect every step, but the fact is you make in all the condition the worst case, by checking step by step.
(4) Mergesort
Worst case space complexity, O(n)
the mergesort is similar to insertion sort.
Instead of making sure that first k items is sorted, mergesort makes sure the all the subparts are sorted.
This is a good use of recursion - saves times of typing.
def _merge_1(left, right):
"""Merge sorted lists left and right into a new list and return that new
list."""
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def _mergesort_1(L):
"""Return a new list that is a sorted version of list L."""
if len(L) < 2:
return L[:]
else:
middle = len(L) // 2
left = _mergesort_1(L[:middle])
right = _mergesort_1(L[middle:])
return _merge_1(left, right)
There are many version of mergesort. They are with the character that divide all the items into smaller part (which small enough) and sort them and merge them together.
Because of the different way of dividing, I think "their worst cases" are different, although in the same time complexity
(5) Quicksort
O(n log n) expected time complexity follows.
Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The worst case for quick sort is that the list is already sorted. Since in that case each iteration get two-sublists which one of them has only one item.
However, even in the worst case, it still can match the other sorting program.(shown by the data in the our lab 10)
def _partition_1(L):
"""Rearrange L so that items < L[0] are at the beginning and items >= L[0]
are at the end, and return the new index for L[0]."""
v = L[0]
i = 1
j = len(L) - 1
while i <= j:
if L[i] < v:
i += 1
else:
L[i], L[j] = L[j], L[i]
j -= 1
L[0], L[j] = L[j], L[0]
return j
def _quicksort_1(L):
"""Sort L by partitioning it around the first item, then recursing."""
if len(L) <= 1:
return L
else:
pivot = _partition_1(L)
left = L[:pivot]
right = L[pivot + 1:]
return _quicksort_1(left) + [L[pivot]] + _quicksort_1(right)
One of importance of time complexity is how to define "the time"
For instance, the binary search tree.
By giving a binart search tree with full nodes, what is the time complexity of a function to get a specific number in the tree( with full nodes)? it is O(log n)
Since the worst case is that we need to find the the one in the deep end, however since the tree is 'sorted', each time we can at least exclude half of potential data.
so it is log2(n) => O(log n)
Here, we define each comparison as one time , but in the sorting program above, we define the switch or the change as one time.
When the definition of time complexity is unspecified to be the same, it does not make sense in the formula aspect.
For example, by giving a binart search tree with full nodes, what is the time complexity of a function to get a sorted list consisting of all the elements from the tree?
We could it is O(0) (it makes sense since it is somehow already 'sorted') or O(n), by the two different of time above.
