9. Computational Complexity & Searching (Big O with Search/Sort in Python)

 

프로그램을 돌리는데 시간이 얼마나 소요될 지에 대한 공부이다.

일일히 모든 시간을 다 측정할 수 없으니 Programming에선 자잘한 거 빼고 큰 단위 N으로 Time Complexity를 계산한다.

 

 

-ex) Linear_search / Selection_sort

 

Linear_Search

# Linear Search에서 Timex Complexity 계산해보기
​
def linear_search(lst:list,value:int) -> int :
    for i in range(len(lst)):
        if lst[i] == value:
            return i
    return -1
​
lst = [0,1,4,5,-1,6,100]
print(linear_search(lst,9))
print(linear_search(lst,5))
​
-1
3

 

- 위 list의 크기를 N이라고 가정했을 때, Operation의 실행횟수는 아래와 같다.

 

 

Selection Sort

 

# Selection_sort 에서 Timex Complexity 계산해보기
​
def selection_sort(lst:list) -> None :
    for i in range(len(lst)):
        smallest = i
        
        for j in range(i+1,len(lst)):
            if lst[j] < lst[smallest]:
                smallest = j
        lst[i],lst[smallest] = lst[smallest],lst[i]
​
​
lst = [9,-19,12.5,999,-3,10,0]
selection_sort(lst)
print(lst)
    
​
[-19, -3, 0, 9, 10, 12.5, 999]

 

- 이 역시 위 list의 크기를 N이라고 가정했을 때, Operation의 실행횟수는 아래와 같다.

 

 

 

Operation의 실행 개수를 Count해야 Time Complexity를 Formal하게 계산할 수 있다. --> Big O notation

 

Big O Notation

 

- Big O Notation에서는 항상 최악의 경우/Worst Case를 따진다.

- Order가 큰 Sequence에만 집중한다. 자잘한 단계는 계산에서 Skip

- 한 Sequence에서 최고차항만 다룬다.

- 그 최고차항에서 상수는 Skip

 

--> 위 Selection Sort에서 결국 Time Complexity를 Big O로 표현한다면 : N^2

 

T(N)

 

- 어떤 f(n)이 있을 때, Large n과 constant c에 대해서 f(n) <= c * T(n) 을 만족하는 c가 있을 때 우리는 f(n)의 Big O Notation으로 T(n)을 표현할 수 있다.

 

- 이를 테면, f(N)은 3N^3 + 7N*2 이라고 했을 때 T(N)은 N^3 이라고 할 수 있다. 왜냐하면 10*N^3으로 상수 c를 10만 잡아도 c*T(N)은 항상 f(N)보다 크기 때문이다. 같은 이유로 T(N)을 N^4, N^5로 잡아도 무방하다. 하지만 T(N)을 N^2으로 잡을 순 없다. f(N)의 3N^3 항보다 항상 큰 수식을 만들 수 없기 때문이다.(N은 정말 엄~~~청 큰 숫자가 될 수도 있다고 가정)

 

 

∴ f(N)의 Time Complexity? Big O 관점에서 --> O(N^3)

 

 

- T(N) 예시 추가

Big O 계산할 땐, T(N)의 최고차항! 어느 놈이 Dominant한 지를 잘 파악하자

 

 

 

- Big O 계산용(?) Graph

 

n*log(n)의 위치 주목, 앞으로 자주 볼 녀석이다. 참고로 3^n, 5^n .. 등등은 2^n으로 퉁친다.

 

 

Search로 Time Complexity 톺아보기

 

- Linear Search(맨 위 예시) 에선 Time Complexity를 O(N) 보다 줄일 수 없다.

- What if, Input list가 Sorted 라면?? 더 Time Efficient한 Search 가능?

 

Binary Search

 

- 우리는 Sorting이 되어있는 국어사전에서 단어를 찾을 때 첫 장부터 단어를 찾지 않는다.(Using index)

- Middle Term을 자꾸 찔러보면서 단어를 찾는다.

 

lst = [-7,-4,-1,2,4,5,6,10,15,21]
def binary_search(lst:list,value:int) -> int:
    first = 0
    last = len(lst)-1
    while first <= last :
        middle = (first+last) // 2
        if lst[middle] == value:
            return middle
        
        elif lst[middle] > value :
            last = middle - 1
        else :
            first = middle + 1
    return -1
binary_search(lst,7)
-1

 

5th iteration에서 처음으로 valuie 7이 list에 없다는 것을 인

 

 

- Binary Search의 경우 Time Big O?

- Sorted List 라는 가정 하에, Binary Search의 경우 매 횟수를 길이 N에서 Half로 나눠가며 진행한다

- Time Complexcity --> O(logN) --> N이 16이면 보통 반 씩 줄이니까 16=2^4, 4회 / 8=2^3, 3회

- 주로 뭔가 반씩 줄어가는 Algorithm의 경우 Time Complexity는 log(N)으로 본다.

 

※ 1) 만약 Binary Search에서 Duplicate을 포함 한 경우엔 어떻게 할까? 그 Duplicate을 찾을 때 가장 왼쪽 또는 오른쪽에 있는 값의 위치를 찾고 싶다면 어떻게 할까...?

 

※ 2) 만약 Binary Search에서 원하는 값이 없을 때, 그 값보다 작은 또는 큰 값 중에 가장 근사치의 위치를 찾는 방법은..?

 

-- 위 Question들은 다음 Posting에서 한 번 계산해봐야겠다 . .  . 

 

https://eglife.tistory.com/26

9-1 . Binary Search의 여러가지 Case 코딩해보기

 

 

Recursion

 

- 구성요소

 

 1. Base Case : the Simplest case where the algorithm can tirivially conclude without any additional recursive call.

 제일 기본적인 구조, O(1)으로 끝나는 가장 작은 단위의 계산식 // 보통 Empty list or N==1인 경우

 

 2. General Case : the algorithm may call one or more recursive call, to solve exactly the same problems in smaller scale.

똑같은 문제를 repeat하면 안 된다. Recursive call을 할 수록 Scale은 점점 작아져야 함. 아니면 끝나지 않는 알고리즘ㅠ

 

- Binary Search를 Recursion Version으로 코딩

 

lst = [-7,-4,-1,2,4,5,6,10,15,21]
​
def binary_recursion(lst:list,value:int,first:int,last:int) -> None :
    # Base Case
    if first > last : return -1
    
    # General Case
    else :
        mid = (first+last)//2
        if lst[mid] == value :
            return mid
        elif lst[mid] < value :
            return binary_recursion(lst,value,mid+1,last)
        else :
            return binary_recursion(lst,value,first,mid-1)
-----------------------------------------------------------------------
print(binary_recursion(lst,1234,0,len(lst)-1))
print(binary_recursion(lst,10,0,len(lst)-1))
-1
7

 

 

- 위 Binary Search의 Recursion 버전의 경우 Time Complexity는? O(logN)

 

 

 

- 기존 Binary Search 때와 마찬가지로 반씩 쪼개서 recursive call이 들어가고, 각 Call 마다 Coumputing 하는 것은 mid 계산, value 비교, return output(Recursive) 이며 그 것들은 전부 O(1)의 과정들이다. 즉 엄밀히 따지면 O(3*log(N))의 값인데 상수는 무시하기로 했으니 결국 Time Big O는 log(N)으로 기존 Version과 같다.

 

- 이처럼 Recursion의 경우 Time Complexity를 계산하는 것이 좀 껄끄럽당

 

 

- Recursion의 또 다른 예시

 

# 문자를 뒤집어서 써봐라
TEXT = 'I LOVE YOU'
​
# for 문으로 풀기
def sol1(text:str) -> None:
    ans = ''
    for i in range(len(text)):
        ans = ans + text[-(i+1)]
    return ans
sol1(TEXT)
'UOY EVOL I'

----------------------------------------
TEXT
TEXT = 'I LOVE YOU'
​
# Recursion으로 풀기
def sol2(text:str) -> None:
    if not text:
        return text
    else :
        return text[-1] + sol2(text[:-1])
sol2(TEXT)
'UOY EVOL I'

 

- Recurion은 항상 Base Case를 만나서 코드가 끝날 수 있도록 설정을 하자!