너는 네가 알지 못하는 것을 개선할 수 없다. 네 알고리즘의 운행 복잡성을 이해할 수 없다

이 시리즈에서 나는 본고에서 알고리즘의 효율을 어떻게 평가하는지 설명할 것이라고 언급했다.
그런데 왜 당신이 묻는 알고리즘의 효율을 평가합니까?
여러 개의 경로가 한 목적지에 도달할 수 있는 것처럼 우리는 보통 가장 짧은 경로를 사용하는데, 보통 몇 가지 알고리즘으로 계산 문제를 해결한다.알고리즘의 효율을 평가하는 것은 우리가 주어진 계산 문제를 해결하는 가장 짧은 경로를 확정하는 데 도움이 된다.
주어진 임무에 대해 우리는 다음과 같은 측면에서 알고리즘의 효율을 평가한다.
* 작업을 완료하는 데 필요한 공간입니다.이것은 형식적으로 공간의 복잡성이라고 불린다.
* 작업을 완료하는 데 필요한 시간입니다.이것은 형식적으로 시간의 복잡성이라고 불린다.
따라서 알고리즘의 효율을 평가하는 것은 알고리즘의 시공 복잡도를 유도하는 것을 의미한다.
좋아, 그럼 나는 어떻게 알고리즘의 시공 복잡도를 추정해야 합니까?
간단해.알고리즘을 실현하고 컴퓨터에서 실행하며 실행에 필요한 시간과 메모리를 관찰한다.
컴퓨터에서 실행합니까?
멋지다그래서 만약에 우리가 서로 다른 알고리즘의 성능을 비교한다면 우리는 반드시 모든 알고리즘을 실현하고 운행해야 합니까?내 말은 왜 몇 개의 알고리즘을 위해 코드를 작성한 후에 그것을 실행하고 마지막에 하나만 선택해야 하는가?이것은 매우 힘센 방법이다. 내가 말하고 싶은 것은 융통성이 없다.
만약 우리가 이러한 알고리즘의 시공 복잡도에 대해 선험 분석을 한 후에 가장 효율적인 알고리즘을 실현할 수 있다면 어떻게 될까요?
선험 분석?만약 컴퓨터에서 실행되지 않는다면, 우리가 어떻게 알고리즘의 실행 속도를 측정할 수 있겠는가, 아니면 그것이 얼마나 많은 공간을 차지하게 될지.
나는 너에게 어떻게 하는지 알려줄 것이다. 그러나 내가 이렇게 하기 전에, 나는 이 문제를 신속하게 바로잡을 것이다. 봐라, 컴퓨터에서 실행을 통해 알고리즘의 시공 복잡도를 측정하는 것은 심지어 멋있지도 않다.왜?컴퓨터에는 서로 다른 하드웨어가 있다.또한 우리의 알고리즘이 사용하는 실행 시간과 공간도 테스트할 때 실행되는 프로세스 수량의 영향을 받아 얻은 결과가 뚜렷한 오도를 일으킬 수 있다.
오, 이건 일리가 있어.그러면 당신은 나에게 어떻게 이런 선험 분석을 진행할 것을 건의합니까?
간단해!나는 너희들에게 큰 O 기호를 보여 주겠다.
큰 O 기호?바리스다?
이것은 컴퓨터에서 그것을 실행할 필요가 없이 알고리즘의 성능을 설명하는 독특한 방법을 제공했다.Big-O는 최악의 경우 알고리즘이 작업을 수행하는 데 필요한 단계 수가 입력 크기에 따라 어떻게 늘어날지 추정합니다.알고리즘은 항상 일부 데이터에 작용한다. 이런 상황에서 입력한다.따라서 빅오에 대해 우리는 기본적으로 하나의 알고리즘의 성장률과 입력 크기 n 간의 관계를 찾아내려고 시도할 뿐이다. 비록 빅오도 하나의 알고리즘의 공간 복잡도를 추정할 수 있지만 간결하게 보기 위해 본고는 시간 복잡도에 중점을 두려고 한다.
최악의 상황?
예를 들어, Big-O는 반복 목록에 요소가 없는 것으로 가정합니다.이런 상황에서, 우리의 알고리즘은 반드시 목록의 끝까지 순환해야 한다.Big-O의 경우 최악의 상황에서 알고리즘의 성능에만 초점을 맞추고 있습니다.이런 상황에서, 그것은 어쩔 수 없이 가장 어려운 일을 할 것이다.
이 큰 O는 어떻게 알고리즘의 운행 시 복잡성을 측정하는 데 쓰입니까?
실행 시 복잡한 기존 종류가 존재합니다.통상적으로, 그 중 하나는 알고리즘의 운행을 설명할 때 복잡성을 나타낸다.우리는 이곳에서 가장 흔히 볼 수 있는 것을 소개할 것이다.
1. 고정 시간 복잡도 O(1): 만약에 하나의 알고리즘이 하나의 임무를 완성하는데 필요한 걸음 수가 입력 크기가 증가함에 따라 변하지 않는다면 이 알고리즘은 고정 시간 복잡도를 가지고 있다고 한다.

my_list = [1, 2, 3]

first_element = my_list[0]

위의 코드 세션에서 정의된 목록의 크기가 증가하더라도 이 알고리즘은 항상 검색 목록의 첫 번째 작업을 완성해야 한다.
2. 선형 시간 O(n): 이런 알고리즘에 대해 임무를 완성하는 데 필요한 걸음수는 입력 크기와 정비례한다.만약 크기=n을 입력한다면 알고리즘은 n개의 절차를 거쳐 임무를 완성할 것이다.예를 들면 다음과 같습니다.

my_list = [1, 2, 3]

For element in my_list:

    Print(element)

3. 2차 시간 O(n*n): 이런 알고리즘에 대해 하나의 연산을 완성하는 데 필요한 걸음수는 입력 크기의 제곱과 같다.이것은 모든 입력 단원에 대해 선형 시간 연산을 실행하기 때문이다.만약 크기=x를 입력한다면 알고리즘은 x*x의 절차를 거쳐 그 조작을 완성해야 한다

arr = [1,2,3]

For x in arr :

    For y in arr :

        print(x, y)

4. 대수 시간 O(LogN): 이런 알고리즘은 보통 LogN 절차를 통해 임무를 완성한다. 그 중에서 N=입력의 크기는 LogN이 2에서 반드시 끌어올려야 하는 숫자로 N을 제시한다. 예를 들어 N=16이면 Log16=4이다.네가 이미 발견한 바와 같이, 이 종류의 알고리즘은 상대적으로 효과적이다.이 유형의 알고리즘은 어떻게 이런 효율을 실현합니까?모든 단계에서, 그들은 입력 크기를 원시 크기의 절반으로 줄일 것이다.이런 알고리즘의 대표적인 예는 이진 검색 알고리즘이다.

def binary_search(element, arr):

    """ function that searches a 
        sorted list in a binary fashion.
        where element is the search key
        and arr is the list that's to be 
        searched 
    """

    mid_point = len(arr)//2 #floor division

    while True:

        if element == arr[mid_point]:

            print(f"match found at index: {mid_point}")

            break

        elif element > arr[mid_point] and mid_point>0:

            mid_point = len(arr[mid_point: ])//2 + mid_point

            

        elif elem < arr[mid_elem] and mid_elem>0:

            mid_elem = len(arr[:mid_elem])//2

        else:

            print("element not in list")

            break

5. 지수 시간 O(2n):** 이런 알고리즘은 보통 2~n보의 멱이 있어야만 임무를 완성할 수 있다.이런 알고리즘에 대해 그들이 임무를 완성하는 데 필요한 절차 수량은 입력 크기가 증가함에 따라 배로 증가한다.예를 들어 n=3이면 이런 알고리즘은 2에서 3=8의 幂次方이 있어야만 그 임무를 완성할 수 있다.만약 n이 4로 증가한다면 알고리즘은 2에서 4의 멱=16보가 필요할 것이다.보시다시피 걸음수는 8에서 16으로 증가했습니다.
비록 본고는 가장 흔히 볼 수 있는 시간의 복잡성을 토론하였지만, 이곳의 목록은 결코 상세하지 않다.다른 것도 있어요.그 밖에 현실 생활의 소프트웨어 시스템은 일반적으로 복잡한 알고리즘으로 구성되는데 이런 알고리즘은 실제적으로 두 가지 또는 두 가지 이상의 운행 시 복잡성으로 묘사할 수 있다.이런 상황에서 현재 가장 복잡한 운행 시 복잡성에 따라 알고리즘의 성능을 시종 설명해 주십시오. 
계속해서 체인 시계에 관한 다음 글을 주목해 주십시오:)
도구책
www.freecodecamp.org/news/time-is-complex-but-priceless-f0abd015063c/