점근 기호 (2 섹션)

2부로 돌아온 것을 환영합니다. 점근 기호를 소개해 드리겠습니다!일반적인 운영 방식에 대해 계속 논의해 보겠습니다.

일반 운행 시

여러 개의 운행 사례를 깊이 연구하기 전에 프로그램이 가지고 있는 서로 다른 흔한 운행 시간을 살펴보자.다음은 가장 빠른 것부터 가장 느린 것까지 흔히 볼 수 있는 운행 시간을 열거했다.
Θ(1). 이것은 상량 운행 때다.이것은 실행할 때, 입력이 어떻든지 간에 프로그램은 항상 같은 조작을 실행한다.예를 들어 "hello, world"만 출력하는 프로그램은Θ(1)에서 실행됩니다. 왜냐하면 이 프로그램은 항상 "hello, world"만 출력하기 때문입니다.
Θ(대수 N).이것은 대수가 운행할 때이다.검색 알고리즘에서 이 실행을 볼 수 있습니다.
Θ(N).이것은 선형으로 운행할 때이다.전체 데이터 집합을 훑어봐야 할 때, 이런 상황을 자주 볼 수 있습니다.
Θ(N*logN).정렬 알고리즘에서 이 실행을 볼 수 있습니다.
Θ(N2).이것은 다항식이 실행될 때의 예이다.행렬과 같은 2차원 데이터 집합이나 중첩 순환을 검색해야 할 때 이 실행을 볼 수 있습니다.
Θ(2N).이것은 지수가 운행할 때다.귀속 알고리즘에서 이 실행을 자주 볼 수 있습니다. (만약 그것이 무엇인지 모르면 걱정하지 마세요!)
Θ(N!).이것은 계승이 운행할 때다.어떤 사물의 모든 다른 배열을 생성해야 할 때, 이 운행을 자주 볼 수 있습니다.예를 들어 모든 다른 방식으로 알파벳'abcd'를 정렬하는 프로그램이 실행될 때 실행됩니다.

Image credits to Towards Data Science

큰 Ω(Ω) 및 큰 O(O)

때때로 최적 상황과 최악 상황에 대해 프로그램이 서로 다른 운행을 할 수 있다.예를 들어 프로그램의 최적 실행은 Θ(1), 최악 실행은 Θ(N)이다.이런 상황에서 우리는 서로 다른 기호를 사용한다.우리는 대Ω 또는 Ω로 최적 상황을 묘사하고, 대O 또는 O로 최악 상황을 묘사한다.다음 위조 코드를 보십시오. 목록에 12가 있으면 True로 돌아가고, 그렇지 않으면 False로 돌아갑니다.

Function with input that is a list of size N:
    For each value in the list:
        If value is equal to 12:
            Return True
    Return False

순환은 몇 번 교체됩니까?우리 1000호 명세서 한 장 봅시다.목록의 첫 번째 값이 12라면, 순환은 한 번만 교체됩니다.그러나 12가 목록에 없으면 1000번 반복됩니다.입력이 N 크기인 목록이면 목록에 있는 12 개 위치 (또는 목록에 있는지 여부) 에 따라 순환이 1 ~ N 번으로 바뀔 수 있습니다.따라서 가장 좋은 상황에서는 일정한 운행 시간이 있고, 최악의 상황에서는 선형 운행 시간이 있다.
우리는 이 프로그램의 실행 상황을 여러 가지 방식으로 설명할 수 있다.

이 프로그램의 최적 실행은 Θ(1)이다.

이 프로그램의 최악의 실행 시간은 Θ(N)입니다.

이 프로그램의 실행은 Ω(1)이다.

이 프로그램에는 런타임 O(N)가 있습니다.

이 가능하다, ~할 수 있다,...

이 프로그램의 실행은 Θ(N)입니다.

그러나 이것은 사실이 아니다. 왜냐하면 프로그램은 모든 상황에서 선형으로 실행될 때, 최악의 상황에서만 실행되는 것이 아니기 때문이다.
사실상, 운행을 묘사할 때, 사람들은 통상적으로 최악의 상황을 토론한다. 왜냐하면 당신은 항상 최악의 상황을 위해 준비를 해야 하기 때문이다.기술 면접에서 그들은 단지 너에게 한 항목의 대O만 물어볼 때가 많다.

런타임 추가

때때로, 프로그램은 실행을 찾기 어려울 정도로 할 일이 너무 많다.위조 코드 프로그램을 보면 먼저 최대 N의 양수를 인쇄한 다음 N을 2로 나누어 N을 1로 나누는 데 필요한 횟수를 되돌려줍니다.

Function that takes a positive integer N:
    Set a variable i equal to 1
    Loop until i is equal to N:
        Print i
        Increment i

    Set a count variable to 0
    Loop while N is not equal to 1:
        Increment count
        N = N/2
    Return count

이 프로그램을 한 번에 보는 것보다 두 부분으로 나눈다. 첫 번째 순환과 두 번째 순환이다.

첫 번째 순환에서 우리는 N에 도달할 때까지 교체됩니다. 따라서 첫 번째 순환이 실행될 때는Θ(N)입니다.

그러나 이전 연습에서 보듯이 두 번째 순환은 Θ(대수 N)로 실행됩니다.
이제 실행할 때 추가할 수 있습니다. 따라서 실행할 때 Θ(N) + Θ(log N)입니다.

그러나 프로그램의 운행을 분석할 때, 우리는 프로그램의 가장 느린 부분에만 관심을 갖는다. 왜냐하면 Θ(N)는Θ(log N)보다 느리기 때문이다. 우리는 실제로 이 프로그램의 운행시는Θ(N)라고만 말할 뿐이다.각 상황에서 Θ(N)로 실행되면 최악의 경우에도 Θ(N)로 실행되기 때문에 실행할 때도 O(N)라고 할 수 있습니다.대부분의 경우 사람들은 큰 O 기호만 사용한다.