자료구조 01. linear_search, binary_search

2019.03.11 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. linear_search

li라는 list에서 특정한 target의 인덱스를 찾으려면 어떻게 해야할까?
li = [ 5, 7, 2, 8, 3, 9, 1] 이라는 것에서
3이라는 target의 인덱스를 찾을 수 있는 함수를 구현해보자.

linear_search(li, target)--> idx
반환값은 target이 있다면 target의 인덱스
target이 없다면 None을 반환

def linear_search(li, target):
        for i in len(li):
            if li[i] == target:
                return i
        return None      # target이 없으면  None을 반환해라.

굉장히 간단한 함수이다. 하지만 함수의 성능을 보면 굉장히 비효율적으로 볼 수 있다.

알고리즘의 성능차이 비교 절대 시간을 비교 하면 안된다.
컴퓨터 성능이 차이나므로 상대 시간 : 어떤 알고리즘을 실행하는데 해비한 연산의 연산 횟수를 비교하자.
즉 데이터의 갯수에 따른 연산 횟수를 계산해서 성능을 계산하자

이 연산에 + - 등 보다는 그 알고리즘을 구성하는데 가장 헤비하게 미치는 연산은 for문이다.
일반적으로 for문 혹은 if문 비교 연산 if문을 많이 호출하면 느린거고 if문을 조금 호출하면 빠른 것이다.

또한 데이터가 늘어남에 따라 연산횟수가 얼마나 변화하는지를 비교해 봐야 한다.

성능을 평가할떄는 3가지 방법이 있다.

1. 최선의 경우
2. 평균의 경우 --> quick sort
3. 최악의 경우 --> 알고리즘을 말할때는 항상 최악의 경우를 가정한다.
   • 이 알고리즘은 아무리 최악의 경우 몇회의 연산횟수를 보장한다.

성능 평가에 대해 조금 더 공부해보려고 한다.

What does T(n) mean in relation to O(n)?

When discussing an algorithm, the common usage of the symbol 𝑇T is to represent its time complexity.
𝑇T is a function. The input to this function is the input size, the output is the (worst-case) running time for an input of that size.
Therefore, 𝑇(𝑛)T(n) is a number: the number returned by the function 𝑇T when given the number 𝑛n. This number is the running time of our algorithm on an input of size 𝑛n.
The 𝑂O in "𝑂(𝑛)O(n)" is not a function. This is Big O notation. In particular, the symbol 𝑂(𝑛)O(n) represents the class of all functions that grow (asymptotically) at most as quickly as the linear function 𝑓(𝑛)=𝑛f(n)=n.
Big O notation gives us a convenient way to talk about upper bounds. For example, we can say "the time complexity of this algorithm is 𝑂(𝑛2)O(n2)" (formally: "𝑇∈𝑂(𝑛2)T∈O(n2)") to say that the running time of the algorithm is at most quadratic in the input size.
Sometimes, you can see both symbols being used in a single equation. For example, the time complexity of MergeSort is commonly described by the following recurrence: "𝑇(𝑛)=2𝑇(𝑛/2)+𝑂(𝑛)T(n)=2T(n/2)+O(n)".
The meaning of the above statement: For any 𝑛n, the time 𝑇(𝑛)T(n) needed to sort 𝑛n elements can be computed by taking the time 𝑇(𝑛/2)T(n/2) needed to sort 𝑛/2n/2 elements, multiplying that time by 2, and adding something extra. That something extra must be at most linear in 𝑛n.

What does T(n) mean in relation to O(n)? - Quora

해석 :

알고리즘을 논할 때, 기호 T의 일반적인 용도는 시간 복잡성을 나타내는 것이다.

T는 함수다. 이 함수에 대한 입력은 입력 크기, 출력은 해당 크기의 입력에 대한 (최악의) 실행 시간이다.

따라서, T(n)는 숫자다: n을 부여했을 때 T 함수가 반환하는 숫자다. 이 숫자는 크기 n의 입력에 대한 우리의 알고리즘의 실행시간이다.

"O(n)"의 O는 기능이 아니다. 이것은 Big O 표기법이다. 특히 기호 O(n)는 선형 함수 f(n)=n만큼 빠르게(증식적으로) 성장하는 모든 기능의 클래스를 나타낸다.

Big O 표기법은 우리에게 상위에 대해 이야기할 수 있는 편리한 방법을 제공한다. 예를 들어, 우리는 "이 알고리즘의 시간 복잡성은 O(n2)"(공식적으로 "TOO(n2))라고 말할 수 있다.

때때로, 당신은 하나의 방정식에 두 개의 기호가 사용되는 것을 볼 수 있다. 예를 들어, MergeSort의 시간 복잡성은 일반적으로 "T(n)=2T(n/2)+O(n)"에 의해 설명된다.

상기 문장의 의미 : 어떤 n에 대해서도 n 요소를 분류하는데 필요한 T(n/2)는 n/2 요소를 분류하는 데 필요한 시간을 취하고 그 시간을 2로 곱한 후, 어떤 것을 추가함으로써 계산할 수 있다. 그 어떤 특별한 것은 n에 가장 직선적일 것이다.

---->> T 함수는 함수에 대한 최악의 실행시간이다. T(n)은 숫자인데 n 크기에 대한 자료를 함수에 넣었을 때 걸리는 실행시간이다.

---->> 우리가 말하는 알고리즘의 성능이 어떤 것인지 T of N 을 항상 구할 수는 없으므로 big O를 구하는 것을 배운다.

binary_search

def binary_search(li, target):
    """
    binary_search(li, target)--> idx
    반환값은 target이 있다면 target의 인덱스
    target이 없다면 None을 반환
    """

binary_search는 기본적으로 들어오는 자료가 정렬이 되었다고 가정하고 시작한다.
이를 통해 우리는 정렬된 자료의 중간값과 target을 비교하고, target이 중간값보다 작다면
중간값 이후의 배열에는 신경쓰지 않고 중간값이 전의 값들로만 비교하겠다는 것이다.
이를 통해 우리는 for 문을 돌렸을 때보다 훨씬 좋은 성능의 알고리즘을 구현할 수 있다.
(실제로도 많이 쓰이는 알고리즘이다)

구현

def binary_search(li, target):
        start = 0       #(인덱스는 0부터 시작하므로)
        end = len(li) - 1       #(인덱스를 기준으로 해야함으로 1을 빼줘야 한다)
        while start <= end:
                mid = (start + end) // 2
                if li(mid) > target:
                    end = mid - 1
                elif li(mid) < target:
                    start = mid + 1
                else:
                    return mid   # 이러면 실제로 리턴 값에만 들어가게 되므로 시스템적으로 나오는 것은 없다. 따라서 꼭 print를 해서 화면에 나오게 해줘야 한다. or 이 함수를 다른 변수에 할당하고 그 변수를 print하도록 한다.
        return None

[
참고자료] (https://github.com/fabl1106/CS/blob/master/data_structure/binary_search/binary_search.pdf)

새롭게 알게 된 중요한 사실

def exam():
        return 1

exam() 

을 실행해보면 아무것도 나오지 않는다. 숫자 혹은 string을 적어도 마찬가지 이다.

여기서 중요하게 알아야 할 것은 return을 해주는 것은 그 함수에서 리턴 값을 거기에 할당해주는 것이기 때문에 화면에는 나타나지 않는다.
이것을 해결하기 위해서는 return 위에 print 를 적어 화면에 표시하고 싶은 것을 적고 아래에
return 만을 적어서 함수를 빠져나오게 하거나
exam()을 특정변수에 할당해주어서 ( a = exam() ) 그 변수를 print 하는 방법이 있다.

다시 방법을 적어보면

def exam():
        print(1)
        return
exam()        # 이렇게 하면 return 값은 None이 반환된다. 따라서 상황에 따라 return 뒤에 1을 적어줘야 한다.

혹은

def exam():
        return 1

a = exam()
print(a)     #print를 해주어야 한다. 정 위와 같이 해주고 싶다고 하면 exam() 앞에 print를 해주면 된다.

def exam():
        return 1
print(exam())