Problem
Algorithm
Correctness
:We need to use induction
1.Hypothesis
2.Base Case
3.Hypothesis step
efficiency
Ex.
Algorithm A : $3n^2 + 5$
Algorithm B : $7n^2$
$T(A)=T(B)$
upper bound = lower bound
=>Tight bound
Image
This graph is respect of input size.
$logn$ < $n$ < $nlogn$ < $n^2$ < $2^n$
$logn$ ~ $nlogn$ is ok. But $n^2$ and $2^n$ is not ok.
For these alorithms, we need to change these algorithms into either $logn$, $n$, or $nlogn$ due to high time complexity.
| Big-Oh | Static | Theta |
|—————–|—————-|————–|
| Upper Bound | Lower Bound | Tight bound |
| Worst Case | Best Case | Average Case |
lower bound: Find it easily because it is the lowest number
Write a number that finds the largest number in a list(an array) of n numbers.
Base case $k=0$, $k=1$ both are available.
Pseudo code
Can you verify the correctness of algorithms for Exercise1?
Pseudo code
Image
Image
Pseudo code
Ans: $T(n^2)$
T1 : forloop1
T2 : forloop2
$T1(n)$ + $T2(n)$ = $T(n)$
Pseudo code
Pseudo code
$T(n)$
$T(outerloop)$: n/2
$T(innerloop)$: 1+2+3+…+n/2
$T(n)$ = $\frac{n}{2}$ x $\frac{(1 + n/2)}{2}$
Container
:A collection of objects.(e.g.vector,list,set, …)
Interface
:A collection of operations.(e.g.sequence,set, …)
Datastructure
:A way to store data that supports a set of operations.
Container and Interface are part of a Datastructure.
Set Interface
|Container | Static | Dynamic | Order |
|——————|———–|————————-|———————————————————-|
|build(A)
len()| find(k) | insert(x)
delete(x) | find_min()
find_max()
find_prev()
find_next()|
build(A): Put student data one by one in a set.
데이터를 자료구조 안에 넣는 동작이다.
find(k): find the student or object that one wants to find according to the studentID or key
insert(x), delete(x): It is dynamic because the object contained changes during the runtime.
k stands for key.
Set Datastructure
| | Container | Static | Dynamic | Order |
|—————-|——————|————-|—————————–|—————————————————————–|
| | build(A) | find(k) | insert(x)
delete(x) | find_min()
find_max() | find_next()
find_prev() |
| Unsorted Array | n | n | n | n |
| Sorted Array | ? | logn | n | 1 | logn |
find(k):
Suppose a situation when we want to find a student with a specific student ID. In the worst case, the student could be situated in the end of the set.
That’s why we use Big-O and the time complexity is n in the unsorted array.
insert(x),delete(x): Its time complexity is ‘n’ cause we have to fill in the value irrelevent whether sorted or not.
find_min(),find_max(): When it is sorted, we can find it immediately. So the time complexity is one.
find(k):
Think of Binary Search.
$\frac{n}{2}$ $x$ $\frac{1}{2}$ $x$…
find_next(),find_prev(): This operation finds the value next or previous to the value that we want to find. That’s why its time complexity is logn.
Exactly the same with find(k).
build(A): Building a set itself takes about n time complexity. So the total time complexity should be inevitably more than n. So the best time complexity
for the set datastructure is nlogn, which is slightly higher than n.
Vocabulary : Sorting
Destructive: Overwrites the input array
-It is in an operation that modifies the original data structure, set. It modifies the original set and also creates a new set with the modified contents.
-It is useful when memory usage is in concern or if you want avoid making unnecessary copies of data.
-ex.Suppose we are sorting a new memory to find the person with the largest number. It would be a waste of memory to save all the data one by one.
In place: Uses O(1) extra space
-It is in an operation that modifies the original data structure, set. It modifies the original set directly without creating a new set.
-It doesn’t allocate similar or bigger data.
-It operates without taking up extra space and the sorting spends constant time.
Permutation Sort
-permutation: n만큼 가지고 있으면 얘가 가지는 모든 경우의 수를 다 봄
-ordering을 하지 않고 둘만 잠깐 바꿔보자.
Algorithm
1.Throws the number randomly.
랜덤하게 특정 숫자를 던진다
2.Check whether the number is sorted or not.
특정 숫자가 정렬이 돼있는지 여부를 확인
3.If sorted, then return the sorted array.
만약 정렬이 돼있다면 정렬된 배열을 돌려줌.
4.Otherwise it again generate another randomization of numbers until the array is sorted.
안 돼있다면 또 다른 랜덤한 숫자를 생성해 배열이 정렬될 때까지 생성함.
Geeks Pseudo code
while not Sorted(list) do:
shuffle(list)
done
Professor’s Idea
1)Enumerate
2) check if it is sorted
i 1 to n-1
B[n] <= B[n-1]
Time Complexity(lower bound): $n!x(n-1)$
n!: random하게 어떤 조합을 만듦
n-1: sort돼 있는지 확인
Professor’s Pseudo Code
def permutation_sort(A):
for B in permutations(A):
if is_sorted(B):
return B
Permutation Sort Example A = [3,1,2]
1) generate the firt permutation array [3,1,2]
2) Check if the firt permutation array is in sorted order. In this case, [3,1,2] is not in sorted order, so move on to the next permutation.
3) Generate the next permutation of the array [3,1,2]. The next permutation is [3,2,1].
4) Check if the next permutation is in the sorted order. In this case, [3,2,1] is not in sorted order, so move on to the next permutation.
5) Generate the next permutation of the array [3,1,2]. The next permutation is [1,3,2].
6) Check if the next permutation is in the sorted order. In this case, [1,3,2] is not in sorted order, so move on to the next permutation.
7) Generate the next permutation of the array [3,1,2]. The next permutation is [1,2,3].
8) Check if the next permutation is in the sorted order. In this case, [1,2,3] is in sorted order. so return this permutation as the result.
permutation sort geeksforgeeks
Permutation Sort code1 Permutation Sort code2
Set Datastructure: Build(A)
| | Container | Static | Dynamic | Order |
|—————-|——————|————-|—————————–|—————————————————————–|
| | build(A) | find(k) | insert(x)
delete(x) | find_min()
find_max() | find_next()
find_prev() |
| Unsorted Array | n | n | n | n | n |
| Sorted Array | nlogn | logn | n | 1 | logn |
Permutation Sort: $n!*n$
Selection Sort
Merge Sort