점근 기호 (1 섹션)

프로그램을 작성할 때 중요한 것은 코드가 가장 효율적으로 실행될 수 있도록 현명한 프로그래밍 선택을 하는 것이다.컴퓨터는 프로그램을 평가하는 데 시간이 걸리지 않을 것 같지만, 대량의 데이터를 처리하기 위해 프로그램을 확장할 때, 효율적인 코드를 작성하는 것이 성패의 관건이 된다.컴퓨터 과학에서, 우리는 프로그램의 운행 시간을 통해 프로그램의 효율을 정의한다.
그러나 우리는 컴퓨터의 운행 속도가 다르기 때문에 프로그램에만 시간을 계산할 수 없다.먼지투성이인 내 낡은 컴퓨터는 너의 그 새 노트북보다 빨리 달린다.프로그래밍도 많은 다른 언어로 진행되는데, 우리는 어떻게 운행할 때 이 점을 설명합니까?우리는 이러한 가변 요소를 뛰어넘어 프로그램의 운행을 정의하는 일반적인 방법이 필요하다.우리는 점근 부호로 한다.
점근 표현을 사용하면 컴퓨터가 프로그램이 입력한 크기에 따라 실행해야 하는 지령수를 보고 프로그램의 운행 시간을 계산합니다.예를 들어, 만약 내가 집합 중의 최대 원소를 계산하고 있다면, 나는 집합 중의 모든 원소를 검사해야 한다.검사 절차는 어떤 언어를 사용하든 계산을 수행하는 CPU를 사용하든 동일합니다.점근 기수법에서, 우리는 입력의 크기를 N으로 정의합니다. 나는 10개의 원소나 100개의 원소의 집합을 볼 수 있지만, 입력에 비해 얼마나 많은 단계를 수행했는지 알기만 하면 특정한 숫자를 N으로 대체할 수 있습니다.두 번째 입력이 있으면 입력 크기를 M으로 정의할 수 있습니다.
각양각색의 점근 기호가 있고 서로 다른 관심사에 중심을 둔다.어떤 사람들은 프로그램의 가장 좋은 상황을 전달할 수 있다.예를 들어, 만약 우리가 집합에서 값을 검색한다면, 가장 좋은 상황은 우리가 첫 번째로 찾은 위치에서 이 요소를 찾는 것이다.다른 유형은 최악의 상황을 주목할 것이다. 예를 들어 우리가 값을 검색하면 전체 데이터를 집중적으로 찾지만 그것을 찾지 못한다.일반적으로 프로그래머는 최악의 상황에 전념하기 때문에 통신의 운행 시 상한선이 존재한다.이것은 "일이 이렇게 나빠지거나 느려질 수도 있지만, 더 나빠지지는 않을 것이다."라는 표현이다.
다음 모듈에서 우리는 점근표현법에 대한 지식을 더 많이 배울 것이다. 점근표현법을 통해 프로그램의 운행을 정확하게 분석하는 방법, 프로그램을 만들 때 서로 다른 데이터 구조와 알고리즘의 운행을 고려하는 방법을 배울 것이다.이러한 기술을 배우면 프로그램을 설계할 때의 사고방식을 바꾸고 소프트웨어 공학 세계를 위해 준비를 할 수 있다. 이 세계에서 효율적인 프로그램을 만드는 것은 기본적인 기술이다.

무엇이 점근 기호입니까?

치타페라리.생활다 빨라요. 그런데 뭐가 제일 빠른지 어떻게 알아요?너는 속도계로 치타와 파라리의 속도를 측정할 수 있다.너는 해와 달로 생명을 평가할 수 있다.
그런데 컴퓨터 프로그램은요?사실상, 너는 컴퓨터 프로그램에 시간을 재줄 수 있지만, 서로 다른 컴퓨터의 운행 속도는 다르다.예를 들어 한 컴퓨터에 12나초가 걸리는 프로그램은 다른 컴퓨터에 45밀리초가 걸릴 수 있다.따라서 우리는 프로그램의 운행 시간을 측정하는 더 일반적인 방법이 필요하다.우리는 점근 부호로 한다.
우리는 컴퓨터가 프로그램이 입력한 크기에 따라 얼마나 많은 명령을 실행해야 하는지를 보면서 프로그램의 운행 시간을 계산할 수 있다. 점진 표현법을 통해 프로그램의 시간을 계산하는 것이 아니라: N.
예를 들어, N 크기를 입력한 프로그램은 컴퓨터에 5N2+3N+2 명령을 실행하라고 알려줄 수 있습니다.(우리는 미래의 연습에서 어떻게 이런 표현을 얻을 수 있는지 연구할 것이다.)그러나 이것은 여전히 상당히 혼란스럽고 방대한 표현이다.점근 표현법에 대해 우리는 모든 상수(숫자)를 제거했다. 왜냐하면 N이 매우 커지면 상수에 미세한 차이가 생기기 때문이다.상수를 변경한 후, 우리는 N2+N을 얻었다. 만약 우리가 표현식에서 이 항목의 모든 항목을 취하여 그림으로 그린다면, 우리는 N2 항목이 N 항목보다 더 빨리 증가하는 것을 볼 수 있을 것이다.

Image credits to Algorithms And Me
예를 들어, N이 1000인 경우:

N2 1000000

N은 1000

보시다시피 N2항은 N항보다 훨씬 중요합니다.N이 1000보다 크면 차이가 더욱 커집니다.이렇게 큰 차이가 있기 때문에, 우리는 운행을 계산할 때 심지어 N 항목을 고려할 필요가 없다.따라서 이 프로그램에 대해 우리는 N2로 실행할 때를 설명할 것이다.우리는 이 프로그램의 운행 시간을 세 가지 다른 방식으로 설명할 수 있다. 그것이 바로 큰 θ또는Θ(N2), 큰 O나 O(N2), 큰 ω또는Ω(N2)이다.

대θ(Θ)

우리가 탐구하고자 하는 첫 번째 점근 기호는 대θ이다.프로그램이 실행될 때 하나의 상황만 있을 때, 우리는 큰 θ를 사용한다.그러나 이것은 도대체 무엇을 의미하는가?다음 목록의 값을 인쇄하는 함수의 위조 코드를 보십시오.

Function with input that is a list of size N:
   For each value in list:
    Print the value

컴퓨터가 실행해야 하는 지령의 수량은 순환이 진행될 교체 횟수에 달려 있다. 순환이 더 많이 진행되면 컴퓨터가 지령을 실행하기 때문이다.이제 순환이 몇 번 교체될지 봅시다. 이것은 N의 값에 달려 있습니다.
우리가 모든 상황에서 보듯이 크기가 N인 목록에 대해 프로그램이 실행될 때 N이다. 왜냐하면 프로그램은 N차 값을 인쇄해야 하기 때문이다.따라서 실행할 때는Θ(N)라고 할 수 있습니다.
우리 좀 더 복잡한 예를 봅시다.아래의 위조 코드 프로그램에서 이 함수는 정수 N을 취하고 N을 2로 나누어 N이 1에 도달하는 데 필요한 횟수를 계산한다.

Function that has integer input N:
  Set a count variable to 0
  Loop while N is not equal to 1:
      Increment count
      N = N/2
  Return count

그러나 한 프로그램이 여러 개 실행될 때 사례는 어떻게 될까요?다음 주에 두 번째 파트 계속 주목!