점근 기호 (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인 경우:
대θ(Θ)
우리가 탐구하고자 하는 첫 번째 점근 기호는 대θ이다.프로그램이 실행될 때 하나의 상황만 있을 때, 우리는 큰 θ를 사용한다.그러나 이것은 도대체 무엇을 의미하는가?다음 목록의 값을 인쇄하는 함수의 위조 코드를 보십시오.
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
그러나 한 프로그램이 여러 개 실행될 때 사례는 어떻게 될까요?다음 주에 두 번째 파트 계속 주목!
Reference
이 문제에 관하여(점근 기호 (1 섹션)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/wdiep10/asymptotic-notation-part-1-3g7j텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)