알고리즘으로 추상 기계 사용하기 - 더미

알고리즘에 필요한 작업이 많을수록 복잡해집니다. 복잡성은 각 작업에 시간이 걸리기 때문에 시간 사용량 측면에서 알고리즘 효율을 측정 한 것입니다. 복잡한 알고리즘은 더 많은 시간이 필요하기 때문에 같은 문제가 주어지면 복잡한 알고리즘은 일반적으로 간단한 알고리즘보다 덜 유리합니다.

의료 또는 금융 분야 나 비행기 또는 우주 로켓의 자동 조종사로 비행하는 경우와 같이 실행 속도가 차이가 나는 경우를 생각해보십시오. 알고리즘의 복잡성을 측정하는 것은 어려운 작업이지만 올바른 솔루션을 원한다면 필요한 작업입니다. 첫 번째 측정 기술은 RAM (Random Access Machine)과 같은 추상 기계를 사용합니다.

RAM은 컴퓨터가 프로그램을 실행할 때 사용하는 내부 메모리 인 Random-Access Memory의 약자입니다. 동일한 머리 글자 어를 사용하더라도 Random-Access Machine은 완전히 다른 무언가입니다.

추상 기계는 실제 컴퓨터가 아니라 이론적 인 컴퓨터로, 컴퓨터는 기능 상 상상할 수 있습니다. 추상 머신을 사용하여 실제로 테스트 할 필요없이 알고리즘을 컴퓨터에서 얼마나 잘 사용할 수 있을지 생각해보십시오.하지만 사용하려는 하드웨어 유형에 구속을받습니다. RAM 컴퓨터는 기본적인 산술 연산을 수행하고 메모리의 정보와 상호 작용합니다. RAM 컴퓨터가 모든 작업을 수행 할 때마다 시간 단계 (시간 단위)가 필요합니다. RAM 시뮬레이션에서 알고리즘을 평가할 때 다음 절차를 사용하여 시간 단계를 계산합니다.

각각의 간단한 연산 (산술 연산)을 시간 간격으로 계산합니다.

1. 복잡한 연산을 간단한 산술 연산으로 나누고 1 단계에서 정의한 시간 단계를 계산합니다.
2. 메모리에서 모든 데이터 액세스를 한 번 단계로 계산합니다.
3. 이 계산을 수행하려면 의사 코드 버전의 알고리즘을 작성하고 종이와 연필을 사용하여 이러한 단계를 수행합니다. 결국 컴퓨터가 작동하는 방식에 대한 기본적인 아이디어를 기반으로 한 간단한 접근 방식으로, 하드웨어의 성능과 속도 또는 사용하는 프로그래밍 언어에 관계없이 솔루션을 비교하는 데 유용한 근사값입니다.

표준 및 사전 정의 된 입력을 사용하기 때문에 시뮬레이션을 사용하는 것은 컴퓨터에서 알고리즘을 실행하는 것과 다릅니다. 실제 컴퓨터를 측정하려면 코드를 실행하고 코드를 실행하는 데 필요한 시간을 확인해야합니다. 컴퓨터에서 코드를 실행하는 것은 실제로는 효율성 측정의 또 다른 형태 인 벤치 마크입니다. 응용 프로그램 환경 (예: 사용 된 하드웨어 유형 및 소프트웨어 구현)도 고려해야합니다.벤치 마크는 유용하지만 일반화가 부족합니다. 예를 들어, 최신 하드웨어가 이전 컴퓨터에서 오래 걸린 알고리즘을 신속하게 실행할 수있는 방법을 생각해보십시오.