해당 알고리즘에 따른 프로그램의 시간 효율성. 알고리즘과 데이터 구조의 복잡성과 효율성에 대한 개념. 받은 자료를 어떻게 할 것인가?

알고리즘 효율성알고리즘에서 사용하는 계산 리소스와 관련된 알고리즘의 속성입니다. 알고리즘에 필요한 리소스를 결정하려면 알고리즘을 분석해야 합니다. 알고리즘 효율성은 반복적이거나 연속적인 프로세스의 제조 생산성과 유사하다고 생각할 수 있습니다.

효율성을 극대화하기 위해 리소스 사용량을 줄이고 싶습니다. 그러나 서로 다른 리소스(예: 시간 및 메모리)는 직접 비교할 수 없으므로 두 알고리즘 중 어느 것이 더 효율적인 것으로 간주되는지는 종종 고속 요구 사항, 최소 메모리 사용량 또는 다른 측정 방법과 같이 어느 요소가 더 중요한지에 따라 달라집니다. 능률.

이 글을 참고해주세요 아니다프로그램 최적화, 컴파일러 최적화 기사에서 논의되는 알고리즘 최적화에 대해 사이클 최적화, 객체 코드 최적화 프로그램, 등등. "최적화"라는 용어 자체는 오해의 소지가 있습니다. 수행할 수 있는 모든 것이 "개선"이라는 범위에 속하기 때문입니다.

배경

실행 시간에 중점을 두고 효율성의 중요성은 1843년 Charles Babbage의 기계 분석 엔진과 관련하여 Ada Lovelace에 의해 강조되었습니다.

“거의 모든 컴퓨팅에는 프로세스를 성공적으로 완료하기 위해 다양한 구성 선택이 가능하며 다양한 규칙이 계산 수행 목적의 선택에 영향을 미칩니다. 중요한 것은 계산을 수행하는 데 필요한 시간을 최소화할 수 있는 구성을 선택하는 것입니다."

초기 전자 컴퓨터는 속도와 메모리 측면에서 매우 제한적이었습니다. 어떤 경우에는 작업이 빠른 속도를 달성하기 위해 많은 양의 메모리를 사용하거나 적은 양의 작업 메모리를 사용하는 느린 알고리즘을 사용해야 하는 시간-메모리 상충 관계가 있다는 것이 인식되었습니다. 이 경우 사용 가능한 메모리가 충분한 가장 빠른 알고리즘이 사용되었습니다.

최신 컴퓨터는 초기 컴퓨터보다 훨씬 빠르며 훨씬 더 많은 메모리(킬로바이트 대신 기가바이트)를 가지고 있습니다. 그러나 Donald Knuth는 효율성이 여전히 중요한 요소임을 강조합니다.

"기존 엔지니어링 분야에서는 12% 개선이 쉽게 달성 가능하며 결코 금지된 것으로 간주되지 않았습니다. 프로그래밍에서도 마찬가지여야 한다고 믿습니다."

검토

리소스 소비(또는 리소스 비용)가 허용 가능한 수준 이하이면 알고리즘이 효율적인 것으로 간주됩니다. 대략적으로 말하면, 여기서 "허용 가능"은 "알고리즘이 사용 가능한 컴퓨터에서 합리적인 시간 동안 실행됩니다"를 의미합니다. 1950년대 이후 컴퓨터의 처리 능력과 사용 가능한 메모리가 크게 증가했기 때문에 현재의 '허용 가능한 수준'은 10년 전만 해도 받아들일 수 없는 수준이었습니다.

컴퓨터 제조업체는 정기적으로 새로운 모델을 출시하며, 종종 더 강력한 모델을 출시합니다. 소프트웨어 비용은 상당히 높을 수 있으므로 어떤 경우에는 기존 컴퓨터와 호환되는 더 빠른 컴퓨터를 구입하여 더 나은 성능을 얻는 것이 더 쉽고 저렴합니다.

알고리즘에서 사용하는 리소스를 측정하는 방법에는 여러 가지가 있습니다. 가장 많이 사용되는 두 가지 측정 방법은 속도와 사용된 메모리입니다. 다른 측정에는 전송 속도, 임시 디스크 사용량, 장기 디스크 사용량, 전력 소비, 총 소유 비용, 외부 신호에 대한 응답 시간 등이 포함될 수 있습니다. 이러한 측정값 중 상당수는 알고리즘의 입력 데이터 크기(즉, 데이터 처리가 필요한 수량)에 따라 달라집니다. 측정값은 데이터가 표시되는 방식에 따라 달라질 수도 있습니다(예를 들어 일부 정렬 알고리즘은 이미 정렬된 데이터에서 성능이 저하되거나 데이터가 역순으로 정렬되는 경우).

실제로 필요한 정확도 및/또는 신뢰성과 같이 알고리즘의 효율성에 영향을 미치는 다른 요소가 있습니다. 아래 설명된 바와 같이, 알고리즘이 구현되는 방식도 실제 성능에 상당한 영향을 미칠 수 있지만, 구현의 많은 측면은 최적화 문제입니다.

이론적 분석

알고리즘의 이론적 분석에서는 점근적 동작으로 알고리즘의 복잡도를 추정하는 것, 즉 알고리즘의 복잡도를 입력 크기의 함수로 반영하는 것이 일반적인 관행입니다. N Big O 표기법이 사용됩니다. 이 추정치는 일반적으로 대규모의 경우 상당히 정확합니다. N, 그러나 작은 값에서는 잘못된 결론으로 이어질 수 있음 N(따라서 느린 것으로 간주되는 버블 정렬은 몇 가지 요소만 정렬하면 되는 경우 빠른 정렬보다 빠를 수 있습니다.)

지정	이름	예
O(1) (\표시스타일 O(1)\,)	영구적인	숫자가 짝수인지 홀수인지 확인합니다. 일정한 크기의 조회 테이블을 사용합니다. 적절한 해시 함수를 사용하여 요소를 선택합니다.
O (log ⁡ n) (\displaystyle O(\log n)\,)	대수적	이항 힙에 대한 작업과 유사하게 이진 검색 또는 균형 트리를 사용하여 정렬된 배열에서 요소를 찾습니다.
O(n) (\표시스타일 O(n)\,)	선의	정렬되지 않은 목록이나 불균형 트리에서 요소 찾기(최악의 경우) 2개 추가 N- 단대단 캐리(end-to-end carry)를 사용하는 비트 수.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	준선형, 로그 선형	빠른 푸리에 변환 계산, 힙 정렬, 퀵 정렬(최적 및 평균 사례), 병합 정렬
O (n 2) (\displaystyle O(n^(2))\,)	정사각형	2를 곱하기 N- 간단한 알고리즘을 이용한 숫자 정렬, 버블 정렬(최악의 경우), 쉘 정렬, 퀵 정렬(최악의 경우), 선택 정렬, 삽입 정렬
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	지수	동적 프로그래밍을 사용하여 여행하는 외판원 문제에 대한 (정확한) 해결책을 찾습니다. 완전 검색을 사용하여 두 논리문이 동일한지 확인

검증 테스트: 성능 측정

새로운 버전의 소프트웨어의 경우 또는 경쟁 시스템과의 비교를 제공하기 위해 벤치마크를 사용하여 알고리즘의 상대적 성능을 비교하는 경우가 있습니다. 예를 들어, 새로운 정렬 알고리즘이 출시되면 이전 알고리즘과 비교하여 해당 알고리즘이 알려진 데이터에 대해 다른 알고리즘만큼 효율적인지 확인할 수 있습니다. 성능 테스트는 사용자가 다양한 제조업체의 제품을 비교하여 기능 및 성능 측면에서 요구 사항에 가장 적합한 제품을 평가하는 데 사용할 수 있습니다.

일부 벤치마크 테스트는 Roy Longbottom의 PC Benchmark Collection과 같은 다양한 컴파일 및 해석 언어에 대한 비교 분석을 제공합니다. 컴퓨터 언어 벤치마크 게임일부 프로그래밍 언어의 일반적인 작업 구현 성능을 비교합니다.

구현 문제

구현 문제는 실제 성능에도 영향을 미칠 수 있습니다. 여기에는 프로그래밍 언어 선택, 알고리즘이 실제로 코딩되는 방식, 선택한 언어에 대한 번역기 선택, 사용되는 컴파일러 옵션, 심지어 사용되는 운영 체제까지 포함됩니다. 어떤 경우에는 인터프리터로 구현된 언어가 컴파일러로 구현된 언어보다 훨씬 느릴 수 있습니다.

프로그래머가 제어할 수 없는 타이밍이나 메모리 사용에 영향을 미칠 수 있는 다른 요소가 있습니다. 여기에는 데이터 정렬, 자세히, 가비지 수집 , 명령 수준 병렬 처리 및 서브루틴 호출 .

일부 프로세서에는 벡터 연산을 수행하는 기능이 있어 한 번의 연산으로 여러 피연산자를 처리할 수 있습니다. 프로그래밍이나 컴파일 수준에서 이러한 기능을 사용하는 것은 쉽지 않을 수도 있습니다. 순차 컴퓨팅을 위해 설계된 알고리즘은 병렬 컴퓨팅을 수용하기 위해 완전한 재설계가 필요할 수 있습니다.

명령이 다르게 구현되어 일부 모델의 명령이 다른 모델에서는 상대적으로 느려질 수 있는 프로세서 호환성과 관련된 또 다른 문제가 발생할 수 있습니다. 이는 최적화 컴파일러에 문제가 될 수 있습니다.

리소스 사용량 측정

측정값은 일반적으로 입구 크기의 함수로 표현됩니다. N.

가장 중요한 두 가지 차원은 다음과 같습니다.

시간: 알고리즘이 CPU를 사용하는 데 걸리는 시간입니다.
메모리: 알고리즘에 필요한 작업 메모리(일반적으로 RAM)의 양입니다. 여기에는 코드에 대한 메모리 양과 코드가 작동하는 데이터에 대한 메모리 양이라는 두 가지 측면이 있습니다.

배터리로 구동되는 컴퓨터(예: 노트북) 또는 매우 길고/큰 계산(예: 슈퍼컴퓨터)의 경우 다른 종류의 측정이 필요합니다.

직접적인 에너지 소비: 컴퓨터를 작동하는데 필요한 에너지.
간접 에너지 소비: 냉방, 조명 등에 필요한 에너지

어떤 경우에는 덜 일반적인 측정이 필요합니다.

기어 크기: 대역폭이 제한 요소일 수 있습니다. 압축을 사용하면 전송되는 데이터의 양을 줄일 수 있습니다. 그래픽이나 이미지(예: Google 로고)를 표시하면 수만 바이트(이 경우 48K)가 전송될 수 있습니다. 이를 "Google"이라는 단어의 6바이트를 전송하는 것과 비교해 보세요.
외부 메모리: 디스크나 기타 외부 저장 장치에 필요한 메모리입니다. 이 메모리는 임시 저장 또는 향후 사용을 위해 사용될 수 있습니다.
응답 시간: 이 설정은 컴퓨터가 외부 이벤트에 빠르게 응답해야 하는 실시간 응용 프로그램에 특히 중요합니다.
총 소유 비용: 단일 알고리즘을 실행하려는 경우 매개변수가 중요합니다.

시간

이론

이러한 유형의 테스트는 프로그래밍 언어, 컴파일러 및 해당 옵션의 선택에 따라 크게 달라지므로 비교된 알고리즘은 동일한 조건에서 구현되어야 합니다.

메모리

이 섹션에서는 알고리즘에 필요한 주 메모리(종종 RAM)의 사용을 다룹니다. 위의 타이밍 분석과 마찬가지로 알고리즘 분석은 일반적으로 다음을 사용합니다. 알고리즘의 공간적 복잡성입력 크기의 함수로 필요한 런타임 메모리를 추정합니다. 결과는 일반적으로 "O" 빅으로 표현됩니다.

메모리 사용에는 네 가지 측면이 있습니다.

알고리즘 코드를 저장하는 데 필요한 메모리 양입니다.
입력 데이터에 필요한 메모리 양입니다.
출력에 필요한 메모리 양(정렬과 같은 일부 알고리즘은 입력을 자주 재배열하며 출력에 추가 메모리가 필요하지 않음)
계산 중 계산 프로세스에 필요한 메모리 양(여기에는 명명된 변수와 서브루틴 호출에 필요한 스택 공간이 포함되며 이는 재귀를 사용할 때 중요할 수 있습니다).

초기 전자 컴퓨터와 가정용 컴퓨터는 작업 기억 용량이 상대적으로 작았습니다. 따라서 1949년에 EDSAC는 1024개의 17비트 단어의 최대 작업 메모리를 가지고 있었고, 1980년에는 1024바이트의 작업 메모리를 갖춘 Sinclair ZX80이 출시되었습니다.

최신 컴퓨터는 상대적으로 많은 양의 메모리(아마도 기가바이트)를 가질 수 있으므로 알고리즘에 사용되는 메모리를 특정 양의 메모리로 압축하는 것이 이전보다 덜 필요합니다. 그러나 세 가지 다른 범주의 기억이 존재한다는 것은 중요합니다.

캐시(종종 정적 RAM) - CPU와 비슷한 속도로 실행됩니다.
주 물리적 메모리(종종 동적 RAM) - CPU보다 약간 느리게 실행됩니다.
가상 메모리(종종 디스크에 있음) - 거대한 메모리처럼 보이지만 RAM보다 수천 배 느리게 작동합니다.

필요한 메모리가 컴퓨터 캐시에 맞는 알고리즘은 주 메모리에 맞는 알고리즘보다 훨씬 빠르며, 결과적으로 가상 공간을 사용하는 알고리즘보다 훨씬 빠릅니다. 문제를 복잡하게 만드는 것은 일부 시스템에 최대 3가지 수준의 캐시가 있다는 사실입니다. 시스템마다 이러한 유형의 메모리 양이 다르기 때문에 알고리즘에 대한 메모리 효과는 시스템마다 크게 다를 수 있습니다.

전자 컴퓨팅 초기에는 알고리즘과 데이터가 메인 메모리에 맞지 않으면 사용할 수 없었습니다. 요즘 가상 메모리를 사용하면 대용량 메모리가 제공되지만 성능이 저하됩니다. 알고리즘과 해당 데이터가 캐시에 맞으면 매우 빠른 속도를 얻을 수 있으므로 필요한 메모리를 최소화하면 시간을 최소화하는 데 도움이 됩니다. 캐시에 완전히 들어맞지는 않지만 다음을 제공하는 알고리즘 링크의 지역성, 비교적 빠르게 작업할 수 있습니다.

효과적인 알고리즘의 예

현재 프로그래밍 상태에 대한 비판

컴퓨터가 빨라지는 것보다 프로그램이 더 빠르게 느려지고 있습니다.

메이는 다음과 같이 말합니다.

광범위한 시스템에서 명령 실행을 절반으로 줄이면 배터리 수명이 두 배로 늘어날 수 있으며 빅 데이터는 더 나은 알고리즘을 위한 기회를 제공합니다. 작업 수를 N x N에서 N x log(N)로 줄이는 것은 큰 N에 강력한 효과가 있습니다... N의 경우 =300억, 이러한 변화는 50년 간의 기술 발전과 유사합니다.

최고의 알고리즘을 위한 경쟁

다음 대회에서는 최고의 알고리즘 개발에 참여하도록 초대하며, 품질 기준은 심사위원이 결정합니다.

또한보십시오

산술 코딩은 엔트로피 코딩의 한 유형입니다. 가변 코드 길이효율적인 데이터 압축을 위해
연관 배열은 사용 시 더욱 효율적으로 만들 수 있는 데이터 구조입니다. 나무 패트리시아또는 주디 배열
성능 테스트 - 특정 상황에서 비교 실행 시간을 측정하는 방법
최고, 최악, 평균 사례- 세 가지 시나리오의 실행 시간을 추정하기 위한 규칙
이진 검색은 정렬된 목록을 검색하는 간단하고 효과적인 기술입니다.
분기 테이블

강의 목표 및 목표: 알고리즘 및 데이터 구조의 복잡성과 효율성을 분석하는 방법 소개

주요 문제: 알고리즘의 효과에 대한 실험적 및 분석적 분석.

N. Wirth의 고전적인 진술 "좋은 프로그램은 잘 고안된 알고리즘과 효과적인 데이터 구조의 통합입니다."

알고리즘 분석
"알고리즘 및 데이터 구조"의 개념은 컴퓨터 기술 분야의 핵심이지만 특정 데이터 구조와 알고리즘을 "고품질 및 효율적"이라고 부르기 위해서는 이를 분석하는 정밀한 기술을 사용해야 합니다. 자연스러운 품질 기준으로 먼저 실행 시간을 강조하는 것은 당연합니다. 또한 소비된 메모리 양과 디스크 공간 리소스, 데이터 액세스 속도(데이터 구조의 효율성)도 중요합니다. 결정의 신뢰성과 신뢰성, 안정성에도주의를 기울여야합니다.

알고리즘은 특정 구현에 묶여서는 안됩니다. 사용되는 프로그래밍 도구의 다양성으로 인해 구현이 다른 알고리즘은 효율성이 다른 결과를 생성할 수 있습니다.

데이터 구조에 대한 알고리즘 또는 작업의 실행 시간은 일반적으로 여러 요인에 따라 달라집니다. 알고리즘을 실행하는 데 필요한 시간을 결정하는 가장 간단한 방법은 알고리즘 실행 전후의 시간을 측정하는 것입니다.

그러나 이러한 시간 추정 방법은 정확하지 않다는 점을 기억해야 합니다. 우선 최신 운영 체제에서는 여러 작업이 병렬로 실행될 수 있으며 테스트 케이스 실행이 다른 유형과 결합될 수 있다는 점을 이해해야 합니다. 활동의. 또한 반복 테스트를 수행해야만 안정적인 의존성을 얻을 수 있다는 점을 이해해야합니다. 그렇지 않으면 초기 데이터의 세부 사항에 따라 무작위 요소 작업의 최종 결과에 영향을 미치고 기타 요소, 실행 알고리즘의 시간도 무작위 변수가 됩니다. 연구를 수행할 때 다른 초기 데이터 세트를 사용하여 알고리즘을 실행해야 합니다. 일반적으로 데이터 자체는 무작위로 생성되므로 데이터 세트가 다르기 때문에 소요되는 시간도 달라집니다.

일련의 추정치를 얻은 후에는 그래프를 구성하고 근사화할 수 있습니다.

이러한 분석은 중요하지 않은 알고리즘을 사용할 때 항상 사용해야 합니다. 이는 수십 개의 레코드나 요소로 구성된 평가판 세트가 아닌 전체 실제 데이터를 디버깅에 사용하여 수정이나 수정을 방지하는 애플리케이션 개발 권장 사항과 유사합니다. 나중에 비현실적인 것으로 판명되면 알고리즘이나 구조 데이터를 완전히 재작업합니다. 일련의 실험 결과를 통해 보간 및 외삽을 수행하고 실제 조건에서 알고리즘의 동작을 결정할 수 있습니다.

일반적으로 알고리즘이나 데이터 구조 방식의 실행 시간은 원본 데이터의 크기가 커질수록 증가한다고 할 수 있지만, 크기가 동일하더라도 데이터 유형에 따라 달라지기도 합니다. 또한 실행 시간은 구현, 컴파일이 수행되는 하드웨어(프로세서, 클럭 주파수, 메모리 크기, 디스크 공간 등) 및 소프트웨어(운영 환경, 프로그래밍 언어, 컴파일러, 인터프리터 등)에 따라 달라집니다. 알고리즘 실행. 예를 들어, 다른 모든 조건이 동일하다면 특정 양의 소스 데이터에 대한 알고리즘의 실행 시간은 더 강력한 컴퓨터를 사용하거나 알고리즘을 기계 코드로 프로그램으로 작성할 때 가상 머신에 의한 실행에 비해 더 짧습니다. 이를 바이트코드로 해석합니다.

결론은 알고리즘에 대한 경험적 분석을 수행하는 것은 실제로 신뢰할 수 없다는 것입니다. 주요 단점은 다음 세 가지로 줄일 수 있습니다.

1) 제한된 초기 데이터 세트를 사용하여 실험을 수행할 수 있습니다. 다른 세트를 사용하여 얻은 결과는 고려되지 않습니다.

2) 두 알고리즘의 효율성을 비교하려면 동일한 하드웨어와 소프트웨어에서 실행 시간을 결정하는 실험을 수행해야 합니다.
3) 알고리즘의 실행 시간을 실험적으로 연구하려면 알고리즘의 구현과 실행을 수행해야 합니다.

따라서 우리는 알고리즘을 분석하기 위해 다음과 같은 일반적인 분석 방법을 사용할 필요가 있습니다.

1) 다양한 유형의 입력 데이터를 고려합니다.

2) 하드웨어와 소프트웨어에 관계없이 두 알고리즘의 상대적 효율성을 평가할 수 있습니다.

3) 직접적인 구현이나 실험 없이 알고리즘 설명에 따라 수행할 수 있습니다.

일반 분석의 핵심은 함수 f=f(n1, .., nm)가 특정 알고리즘에 할당된다는 것입니다. 가장 간단한 형태로 이는 입력 데이터의 양인 하나의 변수 n1의 함수입니다. 그러나 계산의 정확성이나 신뢰성 등 다른 변수가 있을 수 있습니다. 따라서 큰 숫자(이진 표현의 길이가 200비트를 초과함)의 경우 특정 숫자가 소수인지 여부를 결정하기 위해 확률적 방법이 사용되며 그 신뢰도는 다양할 수 있습니다. 가장 잘 알려진 함수는 선형, 거듭제곱, 로그 함수입니다. 그러므로 그들과 함께 일하는 기본 사항을 기억하는 시간을 가져야 합니다.

알고리즘을 구성할 때 첫 번째 단계는 프로그래밍 언어가 아닌 인간 언어로 된 설명을 사용하여 발생합니다. 이러한 설명은 프로그램이 아니지만 동시에 일반 텍스트보다 더 구조화되어 있습니다. 특히, "상위 수준" 설명은 자연어와 일반적인 프로그래밍 언어 구조를 결합하여 접근성이 높으면서도 유익합니다. 이러한 설명은 데이터 구조나 알고리즘의 높은 수준의 분석을 용이하게 합니다. 이러한 설명을 일반적으로 의사코드라고 합니다. 의사코드는 특정 프로그래밍 언어의 코드보다 분석에 더 유용한 경우가 많습니다.

때로는 특정 데이터 구조나 알고리즘과 관련하여 특정 진술을 증명해야 할 필요가 있습니다. 예를 들어, 알고리즘 실행의 정확성과 속도를 입증해야 합니다. 진술을 엄격하게 증명하려면 진술의 증명이나 정당화 역할을 하는 수학적 언어를 사용해야 합니다. 이를 증명하는 몇 가지 간단한 방법이 있습니다.

때때로 진술은 일반화된 형식으로 작성됩니다. “집합 s는 속성 v를 가진 요소 x를 포함합니다. 이 진술을 증명하려면 x가 이 속성을 갖는 s에 "속한다"는 예를 제시하는 것으로 충분합니다. 이러한 일반화된 형식에서는 일반적으로 "집합 s의 모든 요소 x는 속성 P를 갖습니다."와 같이 있을 법하지 않은 진술이 작성됩니다. 이 진술의 오류를 증명하려면 단순히 예를 제시하는 것으로 충분합니다. x는 속성 P가 없는 s에 "속합니다". 이 경우 요소 x는 반례로 작용합니다.

예: n이 1보다 큰 정수이면 2^n - 1 형식의 숫자는 소수라고 명시되어 있습니다. 이 진술은 거짓입니다.

증거:누군가 틀렸다는 것을 증명하려면 반례를 찾아야 합니다.

이는 반대 예입니다: 2^4 - 1 = 15, 15= 3 * 5.

모순에 의한 증명(부정 사용)을 기반으로 하는 또 다른 방법이 있습니다. 이 경우의 주요 방법은 대조와 모순이다. 대비 방법의 사용은 미러링과 유사합니다. "x가 참이면 y는 참입니다"라는 것을 증명하기 위해 "y가 거짓이면 x는 거짓입니다"라고 반대를 주장합니다. 논리적인 관점에서 볼 때, 이들 진술은 동일하지만, 첫 번째 표현과 동치인 두 번째 표현이 더 편리합니다.

예: a*b가 홀수이면 a는 홀수이거나 b는 홀수입니다.

증거:이 명제를 증명하려면 다음과 같은 대조를 고려하십시오. “a가 짝수이고 b가 홀수이면 a*b는 짝수입니다. 일부 정수 x에 대해 a = 2*x라고 가정합니다. 그러면 a*b = 2*i*b이므로 곱 a*b는 짝수입니다.

모순 증명 방법을 사용할 때는 논리를 사용하는 것이 유용합니다.

A 또는 b = a 또는 b를 실행하거나 a와 b를 동시에 실행해야 합니다.
. a와 b = a와 b가 동시에 실행되어야 합니다.
. a xor b = a는 실행해야 하지만 b는 실행하지 않거나 b는 실행해야 하지만 a는 실행하지 않습니다.

명제 q가 참임을 증명하기 위해 모순법을 사용할 때, 먼저 q가 거짓이라고 가정한 다음 그러한 가정이 모순으로 이어진다는 것을 보여줍니다(예: 2 * 2).<>4). 이러한 모순에 도달하면 q가 거짓인 상황은 존재하지 않으며 따라서 q가 참이라고 주장할 수 있습니다.

대부분의 경우 프로그램 실행 시간이나 공간 사용에 대한 설명에서는 정수 매개변수 n(문제의 "크기"를 나타냄)을 사용합니다. 그런 다음 x(n)이라는 진술을 공식화하면 n 값 집합에 대해 그러한 진술은 동일합니다. 이 진술은 "무한한" 숫자 집합에 적용되므로 철저한 직접 증명을 제공하는 것은 불가능합니다. 이러한 상황에서는 유도 방법이 사용됩니다. 유도 방법은 사실에 기초합니다. 이는 모든 n > 1에 대해 발생합니다. 참이라고 알려진 것에서 시작하여 궁극적으로 q(n)이 참이라는 증거로 이어지는 유한한 일련의 동작이 있습니다. 따라서 귀납법에 의한 증명은 n=1,2,3 등에 대해 q(n)이 참이라는 진술로 시작됩니다. 어떤 상수 k까지. 다음으로 우리는 유도 q(n+1), q(n+2)의 다음 "단계"가 n > k에 대해서도 참임을 증명합니다.

알고리즘을 분석하고 작업 수와 실행 시간을 계산할 때 "작은 세부 사항"을 고려해서는 안 되며 상수 요소와 상수는 무시해야 합니다. 실제로는 큰 함수라는 개념이 사용됩니다. 에 대한. 두 개의 함수 f(n)과 g(n)이 있다고 가정하고, f(n)이라고 가정합니다.<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

예를 들어, 배열에서 0과 같은 요소 수를 계산하는 알고리즘은 O(n)으로 설명됩니다. 여기서 n은 요소 수입니다.

1) 20n3+7.2n2-21.78n + 5는 O(n3)으로 설명됩니다.

2)xn-2 + a(0)은 O(xn)으로 설명됩니다.

2) 3*log(n) + log(log(n))는 O(log(n))으로 기술됩니다.

3) 2100은 O(1)로 설명됩니다.

4) 5/n은 O(1/n)으로 설명됩니다.

함수 o(n)은 위에서 목표 시간 비용 함수를 제한하지만 항상 최대 정확도가 있는 함수 O(n)를 선택하도록 노력해야 합니다.

가장 유명한 O 함수를 오름차순으로 나열하면 다음과 같습니다.

점근 분석을 사용할 때 O 표기법을 사용할 때 상수 인자와 덧셈 상수를 무시하는 경우가 많으므로 주의하세요. 그러나 이 값이 충분히 크면 함수 O(1)의 형태가 함수 O(n)에 의해 설명된 알고리즘보다 더 바람직하지만, 물론 실제 적용을 얻는 것은 두 번째 알고리즘입니다.

함수 f(n)의 유형에 따라 다음과 같은 알고리즘 복잡도 클래스가 구별됩니다.

복잡도 함수에 따른 알고리즘 복잡도 클래스
f(n) 보기	알고리즘 클래스의 특성
	대부분의 기능에 대한 대부분의 명령은 한 번 이상 실행됩니다. 프로그램의 모든 명령어에 이 속성이 있으면 프로그램의 실행 시간은 일정합니다.
로그 N	프로그램의 실행 시간이 대수적이면 N이 증가함에 따라 프로그램이 느려집니다. 이러한 실행 시간은 일반적으로 큰 문제를 더 작은 하위 문제 집합으로 줄여 각 단계에서 일정한 요소만큼 문제의 크기를 줄이는 프로그램과 관련됩니다. 밑을 변경해도 로그 값의 변경에는 큰 영향을 미치지 않습니다. n
N	프로그램의 실행 시간이 선형적이라는 것은 일반적으로 각 입력 요소가 거의 처리되지 않는다는 것을 의미합니다.
N로그N	N log N에 비례하는 런타임은 알고리즘이 문제를 더 작은 하위 문제로 나누고 독립적으로 해결한 다음 솔루션을 결합하여 문제를 해결할 때 발생합니다.
엔 2	알고리즘의 실행 시간이 2차인 경우 상대적으로 작은 문제를 해결하는 데 실제로 유용합니다. 2차 실행 시간은 일반적으로 모든 데이터 항목 쌍을 처리하는 알고리즘(아마도 이중 중첩 루프)에 나타납니다.
N 3	세 개의 데이터 요소(아마도 삼중 중첩 루프에서)를 처리하는 유사한 알고리즘은 3차 실행 시간을 가지며 실제로 작은 문제에만 적용 가능합니다.
2N	기하급수적인 실행 시간을 갖는 소수의 알고리즘만이 실제 적용이 가능하지만 이러한 알고리즘은 무차별 대입과 같은 문제를 직접 해결하려고 시도할 때 자연스럽게 발생합니다.

무한대에서 복잡도의 점근 함수를 연구하기 위한 수학적 방법을 기반으로 다섯 가지 알고리즘 클래스가 식별됩니다.

1. 일정한 실행 시간을 갖는 빠른 알고리즘 클래스로, 복잡도 함수는 O(1)입니다. 중간 상태는 역시 이 클래스로 분류되는 복잡도 O(log N)의 알고리즘이 차지합니다.

2. 합리적 또는 다항식 알고리즘의 클래스로, 복잡도 함수는 입력 매개변수로부터 다항식으로 결정됩니다. 예를 들어 O(N), O(N 2, O(N 3)입니다.

3. 복잡도가 O(N log N)인 하위 지수 알고리즘 클래스입니다.

4. 복잡도가 O(2N)인 지수 알고리즘 클래스.

5.과대지수 알고리즘의 클래스. 계승 복잡도를 갖는 알고리즘이 있지만 일반적으로 실제로 적용할 수는 없습니다.

알고리즘 실행 중 메모리 상태는 특정 영역을 할당해야 하는 값에 따라 결정됩니다. 이 경우 문제를 해결하는 과정에서 추가로 셀을 사용할 수 있다. 입력 D에 대해 알고리즘 A에 필요한 메모리 양은 알고리즘 실행 중에 사용되는 최대 메모리 셀 수를 의미합니다. 알고리즘의 용량 복잡도는 알고리즘의 최악의 경우 메모리 용량 함수에 대한 점근적 추정으로 정의됩니다.

따라서 최악의 경우, 평균적인 경우, 최상의 경우에서 알고리즘의 자원 복잡도는 점근적 표기법으로 지정되고 고려 중인 사례에 해당하는 시간 및 용량 복잡도 함수 클래스의 정렬된 쌍으로 정의됩니다.

절차적 프로그래밍의 주요 알고리즘 구성은 다음, 분기 및 반복입니다. 고정된 입력 차원을 사용하여 최상의, 평균 및 최악의 경우에 대한 복잡도 함수를 얻으려면 주요 알고리즘 구조 평가의 차이를 고려해야 합니다.

"Following" 구성의 복잡도는 서로 이어지는 블록의 복잡도의 합입니다: f=f 1 +f 2 +...+f n .
"분기" 설계의 복잡성은 조건에 따라 결정되는 각 명령으로의 전환 확률을 통해 결정됩니다. 동시에 상태를 확인하는 것도 어느 정도 복잡합니다. 최악의 경우의 복잡도를 계산하기 위해서는 가장 복잡도가 높은 분기 블록을 선택하고, 최선의 경우에는 덜 복잡도를 갖는 블록을 선택할 수 있다. f if =f 1 +f 다음 p 다음 +f else (1-p 그러면)
"루프" 구성의 복잡성은 루프 종료 조건(보통 0(1) 차수)을 계산하고 루프 본문의 가능한 최대 작업 수에 루프의 완료된 반복 횟수를 곱하여 결정됩니다. 중첩 루프를 사용하면 복잡성이 배가됩니다.

따라서 알고리즘의 복잡도를 추정하기 위해 복잡도 함수를 구하는 일반적인 방법을 공식화할 수 있다.

알고리즘 분해에는 알고리즘의 기본 구조를 식별하고 복잡성을 추정하는 작업이 포함됩니다. 이 경우 다음과 같은 주요 알고리즘 구조가 고려됩니다.
기본 언어 작업에 대한 노동 강도에 대한 라인별 분석은 누적 분석(모든 작업을 고려) 또는 작업 분석(각 작업의 복잡성을 고려)을 의미합니다.
최상의 경우, 평균적인 경우, 최악의 경우에 대한 기본 알고리즘 구조를 분석하는 방법론을 기반으로 하는 복잡도 함수의 역구성.

재귀 알고리즘의 리소스 효율성을 평가하는 기능은 추가 메모리 비용과 재귀 구성 메커니즘을 고려해야 한다는 것입니다. 따라서 알고리즘의 재귀 구현의 복잡성은 한 번의 재귀 호출 중에 수행되는 작업 수 및 이러한 호출 수와 관련이 있습니다. 값을 반환하고 제어권을 콜 포인트로 이전하는 비용도 고려됩니다. 필요한 스택 메모리를 추정할 때 특정 시점에 스택에 저장되는 재귀 조각이 아니라 일련의 재귀 호출이라는 점을 고려해야 합니다. 따라서 스택 크기는 수신된 동시 재귀 호출의 가능한 최대 수에 따라 결정됩니다.

프로그래머 라이브러리

“디버깅이 오류를 제거하는 과정이라면 프로그래밍은 오류를 도입하는 과정이어야 합니다.”

E. 데이크스트라

1.2. 왜 알고리즘을 공부하는가? 알고리즘의 효율성

첫째, 알고리즘은 컴퓨터 과학의 다양한 영역에서 발생하는 문제를 해결하는 데 필수적인 구성 요소입니다. 알고리즘은 현재 기술 개발 단계에서 핵심적인 역할을 합니다. 여기에서 다음과 같은 일반적인 작업을 기억할 수 있습니다.

다양한 복잡성의 수학 방정식 풀기, 행렬의 곱, 역행렬 찾기;
상품과 사람을 운송하는 최적의 방법을 찾는 것;
다양한 노드(제조업체, 기계, 작업자, 프로세서 등) 간에 리소스를 배포하기 위한 최적의 옵션을 찾습니다.
일치하는 게놈 서열을 찾는 것;
글로벌 인터넷에서 정보를 검색합니다.
전자상거래에서 재정적 결정을 내리기;
오디오 및 비디오 정보 처리 및 분석.

이 목록은 계속 이어지고 있으며 실제로 특정 알고리즘이 사용되지 않는 컴퓨터 과학 및 정보 과학 분야를 찾는 것은 거의 불가능합니다.

둘째, 고품질의 효율적인 알고리즘은 얼핏 보면 컴퓨터 과학(양자 역학, 경제 및 금융, 진화론)과는 거리가 먼 산업에서 획기적인 발전을 이루는 촉매제가 될 수 있습니다.

셋째, 알고리즘을 연구하는 것은 우리의 수학적 능력과 논리적 사고를 발전시키는 매우 흥미로운 과정이기도 합니다.

1.3. 알고리즘의 효율성

컴퓨터의 속도와 메모리 양을 무한정 늘릴 수 있다고 가정해 보겠습니다. 그렇다면 알고리즘을 공부할 필요가 있을까요? 예, 하지만 디커플링 방법의 실행 시간은 유한하고 정답을 제공한다는 점을 보여주기 위한 것입니다. 컴퓨터가 무한히 빠르다면 문제를 해결하기 위한 임의의 올바른 방법이 가능합니다. 물론, 구현하기 더 쉬운 방법이 선택되는 경우가 가장 많습니다.

오늘날 컴퓨터는 매우 강력하지만 속도는 무한하지 않으며 메모리도 무한하지 않습니다. 따라서 미적분학에서는 필요한 메모리 양만큼 리소스가 제한됩니다. 이러한 자원은 현명하게 사용되어야 하며, 이는 시간 및 메모리 자원 사용 측면에서 효율적인 알고리즘을 사용함으로써 촉진됩니다.

동일한 문제를 해결하기 위해 설계된 알고리즘은 종종 효율성이 크게 다를 수 있습니다. 이러한 차이는 다른 하드웨어와 소프트웨어로 인해 발생하는 것보다 훨씬 더 눈에 띌 수 있습니다.

위에서 언급했듯이 이 섹션에서는 정렬 작업에 중점을 둡니다. 고려될 첫 번째 알고리즘인 포함 정렬은 작동하는 데 시간이 필요하며 그 양은 c 1 n 2로 추정됩니다. 여기서 n은 입력 데이터의 크기(정렬할 시퀀스의 요소 수), c입니다. 1은 일정합니다. 이 표현식은 알고리즘의 실행 시간이 소스 데이터의 양에 따라 어떻게 달라지는지 나타냅니다. 포함 정렬의 경우 이 종속성은 2차입니다. 두 번째 알고리즘인 병합 정렬에는 시간이 필요하며 그 양은 2nLog 2n으로 추정됩니다. 일반적으로 포함 정렬 상수는 병합 정렬 상수보다 작습니다. 즉, c12는 ILog 2 n 함수보다 n이 증가함에 따라 더 빠르게 증가합니다. 그리고 어떤 값 n = n 0에 대해 상수 차이의 영향이 더 이상 중요하지 않게 되는 순간에 도달할 것이며 미래에 함수 c 2 nLog 2 n은 모든 n > n 0에 대해 c 1 n 2보다 작아질 것입니다.

이를 입증하기 위해 A와 B라는 두 대의 컴퓨터를 생각해 보십시오. 컴퓨터 A는 더 빠르고 정렬 알고리즘을 실행하며, 컴퓨터 B는 더 느리고 병합 정렬 알고리즘을 실행합니다. 두 컴퓨터 모두 백만 개의 숫자로 구성된 집합을 정렬해야 합니다. 컴퓨터 A는 초당 10억 개의 작업을 수행하고 컴퓨터 B는 천만 개의 작업을 수행한다고 가정하고 B보다 100배 빠르게 실행되는 A가 있습니다. 차이점을 더 눈에 띄게 하기 위해 활성화 메서드에 대한 코드를 최고 전문가가 작성했다고 가정해 보겠습니다. 전 세계의 프로그래머는 프로세서에 명령을 사용하고 이 알고리즘을 사용하여 n개의 숫자를 정렬하려면 2n 2 연산(즉, C 1 = 2)을 수행해야 합니다. 컴퓨터 B의 병합 정렬은 초보 프로그래머가 고급 언어를 사용하여 작성했으며 결과 코드에는 50nlog 2 n 연산(즉, c 2 = 50)이 필요합니다. 따라서 백만 개의 숫자를 정렬하려면 컴퓨터 A가 필요합니다.

그리고 컴퓨터 B -

따라서 나쁜 컴퓨터와 나쁜 컴파일러를 사용하더라도 실행 시간이 더 느리게 증가하는 코드를 사용하면 훨씬 더 적은 CPU 시간이 필요합니다! 10,000,000 자리를 정렬하는 경우 병합 정렬의 이점이 더욱 두드러집니다. 포함 정렬은 이러한 작업에 약 2.3일이 소요되는 반면 병합 정렬의 경우 20분 미만이 소요됩니다. 일반적인 규칙은 정렬할 요소의 수가 많을수록 병합 정렬의 이점이 커진다는 것입니다. 위의 예는 컴퓨터 소프트웨어와 같은 알고리즘이 다음과 같다는 것을 보여줍니다. 기술. 전체 시스템 성능은 하드웨어의 성능만큼 알고리즘의 효율성에 따라 달라집니다.

따라서 가장 단순한 튜링 머신부터 동종 컴퓨팅 환경까지 컴퓨팅 머신에 대한 다양한 옵션이 고려됩니다. 이들 모두는 알고리즘이 존재하는 문제를 해결하는 데 사용될 수 있습니다. 이러한 모델을 기반으로 보다 전문화된 계산 모델, 즉 비분기 산술 프로그램, 비트 계산, 이진 벡터 계산 및 의사결정 트리가 구축됩니다.

알고리즘에는 다음과 같은 특징이 있습니다.

a) 복잡성;

b) 노동 강도;

c) 신뢰성 등

알고리즘의 복잡성을 평가하는 기준은 다양합니다. 가장 자주 우리는 관심을 가질 것입니다 성장 순서입력 데이터의 양이 증가함에 따라 문제를 해결하는 데 필요한 시간과 메모리 용량이 증가합니다. 각각의 특정 작업에 특정 숫자를 연결해 보겠습니다. 크기. 예를 들어, 행렬 곱셈 문제의 크기는 요인 행렬의 가장 큰 크기일 수 있습니다. 그래프의 문제 크기는 주어진 그래프의 모서리 수 등이 될 수 있습니다.

문제 크기의 함수로서 알고리즘에 소요되는 시간을 다음과 같이 부릅니다. 시간 복잡도이 알고리즘. 문제 크기가 증가함에 따라 한계 내에서 이러한 복잡성의 동작을 호출합니다. 점근적 시간 복잡도. 유사하게 정의됨 용량 복잡도그리고 점근적 용량 복잡성.

정형 계산 모델을 고려하는 중요한 동기는 계산 시간에 대한 하한을 얻기 위해 다양한 문제의 계산 복잡성을 밝히려는 욕구입니다. 특정 시간 이내에 주어진 작업을 완료할 수 있는 알고리즘이 없다는 것을 보여주기 위해서는 알고리즘이 무엇인지에 대한 정확하고 때로는 고도로 전문화된 정의가 필요합니다. 그러한 정의의 한 예는 튜링 기계입니다.

4.1.1. 프레임 및 프레임 기계*

두 대의 자동차를 고려하십시오.

1. 메모리에 무작위로 액세스할 수 있는 머신(동일 액세스 주소 머신 - RAM)은 프로그램 명령이 스스로 변경될 수 없는 하나의 덧셈기가 있는 컴퓨터를 모델로 합니다.

2. 저장된 프로그램 모델은 메모리에 대한 무작위 액세스와 명령 수정 기능(RAM*)을 갖춘 기계입니다.

그림 2.9 RAM 머신의 구조(RAM*)

RAM의 경우 프로그램이 메모리에 기록되지 않으므로 프로그램 자체가 수정되지 않습니다. 프로그램은 레이블이 붙은 명령의 시퀀스입니다. 산술 명령어, I/O 명령어, 간접 주소 지정 명령어, 분기 명령어가 있습니다. 모든 계산은 다른 메모리 레지스터와 마찬가지로 임의의 정수를 저장할 수 있는 레지스터 r 0(가산기)에서 수행됩니다. 각 명령은 작업 코드와 주소라는 두 부분으로 구성됩니다. PAM 명령은 어셈블리 언어 명령의 하위 집합입니다. 이 하위 집합은 마음대로 확장할 수 있지만 작업의 복잡성 순서는 변경되지 않습니다.

피연산자는 다음 유형 중 하나일 수 있습니다.

1. =나는전체 숫자 자체를 의미합니다. 나리터럴이라고 불립니다.

2. 나- 내용 등록 나 (나음수가 아니어야 합니다);

3. *나간접 주소 지정을 의미합니다. 즉, 피연산자의 값은 레지스터의 내용입니다. 제이,어디 제이- 레지스터에 있는 정수 나;만약에 제이<0, 차가 멈춘다.

프로그램의 가치를 결정할 수 있습니다. 아르 자형두 개의 개체를 사용합니다. 음수가 아닌 정수 집합에서 정수 집합으로의 매핑 c와 실행할 다음 명령을 결정하는 "명령 카운터"입니다. 함수 c는 메모리 디스플레이,즉 c(i)-레지스터 번호에 포함된 정수 나 (콘텐츠등록하다 나).

처음에는 с(i)=0모든 나 0 , 프로그램 카운터는 P의 첫 번째 명령어로 설정되고 출력 테이프는 비어 있습니다. 실행 후 케이에서 번째 팀 아르 자형카운터가 자동으로 전환됩니다. (k+1)-th(즉, 다음으로) 명령인 경우 케이-저희 팀은 JUMP, HALT, JGTZ 같은 팀은 아니었어요.

RAM* 프로그램은 메모리 레지스터에 있습니다. 각 RAM* 명령은 두 개의 연속적인 메모리 레지스터를 차지합니다. 첫 번째 레지스터에는 연산 코드가 포함되고 두 번째 레지스터에는 주소가 포함됩니다. RAM*에 대한 명령어 세트는 간접 주소 지정을 제외한 모든 항목에서 해당 RAM 세트와 일치합니다. 즉, RAM*은 프로그램 실행 중에 명령어를 변경하여 간접 주소 지정을 시뮬레이션할 수 있습니다.

학생이 솔루션으로 구현한 알고리즘이 특정 초기 데이터를 바탕으로 문제에 대한 정답을 생성할 수 있는지 확인하는 것 외에도 솔루션을 확인할 때 프로그램의 실행 시간도 고려됩니다. 이는 예외 없이 모든 작업에 대해 최적의 알고리즘을 작성하는 것이 매우 중요하다는 것을 의미하지는 않습니다(이는 유능한 구현 및 디버깅에 많은 시간이 걸릴 수 있음). 이는 단순히 일부 개별 작업에서 시간 매개변수가 매우 중요한 역할을 할 수 있음을 의미합니다. 일부 올림피아드 라운드에서는 최적성이 필요한 단일 문제가 없을 수도 있습니다. 그러나 그 반대의 경우도 발생할 수 있습니다.

따라서 학생과 교사 모두 효율성을 기반으로 다양한 알고리즘을 비교할 수 있어야 합니다. 학생-적절한 순간에 문제를 해결하는 가장 적절한 방법을 선택하기 위해 교사는 작업을 유능하게 선택하고 그러한 시간 제한을 정확히 설정할 때 특정 문제의 작성자가 염두에 둔 해결책을 이해합니다.

알고리즘의 효율성을 평가하기 위해 O(“about big”을 읽음)로 표시된 복잡도 함수가 사용됩니다. 실제로 다른 평가도 있지만 학생이 다양한 알고리즘에 익숙해지기 시작하는 단계에서는 실제로 필요하지 않습니다. 복잡도 함수는 소스 데이터나 그 양에 따라 프로그램 실행 시간이 늘어나는 패턴을 반영합니다.

실행 시간이 초기 데이터에 따라 달라지는 알고리즘의 예로는 숫자 N의 모든 자연 약수를 찾는 알고리즘이 있습니다. 분명히 숫자가 클수록 수행해야 하는 루프 단계가 더 많아집니다. 실행 시간이 입력 데이터의 양에 따라 달라지는 알고리즘의 예로는 배열에서 가장 큰 숫자를 검색하는 것입니다. 배열이 길수록 어떤 숫자가 가장 큰지 결정하기 위해 더 많은 비교 작업을 수행해야 합니다.

주요 기능은 다음과 같습니다:

l O(1) - 이러한 복잡도 함수는 프로그램의 실행 시간이 모든 초기 데이터에 대해 일정하다는 것을 나타냅니다.

l O(N) - 작업 수가 N에 비례하여 증가합니다(여기서 N은 작업 매개변수이거나 배열의 요소 수일 수 있음).

l O(log N) - 작업 수는 N의 로그에 비례하여 증가합니다(정확히는 순서가 지정된 배열에서 요소를 검색할 때 반으로 나누는 방법의 복잡성입니다). N이 한 단계씩 증가함에 따라 연산 횟수도 하나씩 변경됩니다. 로그의 밑은 일반적으로 지정되지 않습니다. 우리는 정확한 시간 값이 아니라 성장의 특성(빠름/느림)에 관심이 있습니다.

l O(N2) - N의 제곱에 비례하여 연산 수가 증가합니다. 일반적으로 문제의 복잡성에 따라 O(Nk)가 될 수 있습니다.

l O(N!) - 계승 N에 비례하여 연산 수가 증가합니다.

여기에는 모든 작업이 동일한 시간 동안 수행되지 않는다는 사실로 인해 미묘한 점이 많이 있습니다. 따라서 시간 복잡도를 추정할 때는 가장 많은 시간이 필요한 작업이 사용됩니다.

대부분의 경우 알고리즘을 설명할 때 작동 시간의 추정치는 입력/출력 작업을 고려하지 않고 순수한 형식으로 제공됩니다.

예: 키보드로 배열을 입력하고 그 안에서 가장 큰 요소를 찾는 프로그램의 복잡성을 추정해 보겠습니다.

연산 횟수 N+(N-1)+1=2N을 더해 보겠습니다. 즉, 임의의 N에 대해 연산 횟수가 CN을 초과하지 않는 상수가 있습니다. 따라서 알고리즘의 복잡도는 O(N)입니다.

예: 키보드에서 배열을 입력하고 그 안에서 주어진 속성(예: 특정 값과 동일)을 가진 요소를 찾는 프로그램의 복잡성을 추정해 보겠습니다.

알고리즘은 다음 단계로 구성됩니다.

주어진 속성을 가진 요소를 검색하는 배열 입력(N 입력 작업)(행운: 요소는 배열의 시작 부분이나 맨 끝 부분에 더 가깝게 위치할 수 있습니다. 요소가 존재하지 않으면 다음을 수행해야 합니다. 이를 확인하기 위해 모든 N 비교를 수행하여 결과를 출력합니다.

최선의 경우 이 알고리즘은 N+2 작업(전체 배열의 입력, 단일 비교, 출력)이 필요하고 최악의 경우(해당 요소가 없는 경우 - 2N+1 작업)가 필요합니다. N이 큰 숫자(예: 약 106)인 경우 통일성을 무시할 수 있습니다. 따라서 알고리즘의 복잡도는 O(N)입니다.

예: 대체 방법을 사용하여 길이가 L인 단어 암호화 알고리즘의 복잡도 함수를 결정해 보겠습니다. 알파벳의 각 문자에 대해 대체되어야 하는 문자가 기록된 표가 있다고 가정합니다. 알파벳 S의 글자 수를 나타냅니다.

알고리즘은 다음 단계로 구성됩니다.

단어 입력(1회 작업)은 모든 문자를 반복합니다.

1. 각 문자에 대해 테이블에서 대체 항목을 찾습니다(테이블이 정렬되지 않고 검색을 용이하게 하는 속성이 없는 경우 최악의 경우 검색된 요소가 바로 다음 위치에 있는 경우 한 문자에 대해 S 작업이 있습니다). 끝)

2. 발견된 기호의 출력

사이클의 끝

총 작업 수는 1+(S+1)*L입니다. 충분히 큰 S 및 L 단위를 무시할 수 있는 경우 이 알고리즘의 복잡도 함수는 O(S*L)인 것으로 나타났습니다.

예: 자연수 N을 이진수 체계로 변환하는 알고리즘의 복잡도 함수를 정의해 보겠습니다(데이터 입력 및 출력 작업 없음).

알고리즘은 다음 단계로 구성됩니다.

숫자를 2로 나눈 결과가 0이 될 때까지 반복합니다.

1. 숫자를 2로 나누고 나머지를 기억하세요

2. 나눗셈 결과를 새로운 숫자로 취함

사이클의 끝

총 작업 수는 1+log2N을 초과하지 않습니다. 따라서 이 알고리즘은 O(log N)의 복잡도를 갖는다.

프로그램이 서로 다른 복잡한 기능을 가진 여러 부분으로 구성된 경우 영형더 큰 복잡도 함수는 더 작은 함수를 "흡수"합니다. 예를 들어, O(N) 배열 입력, O(N2) 정렬, 순서 배열 O(N) 출력을 수행하면 전체 프로그램의 복잡성이 O(N2)라고 말할 수 있습니다.

알고리즘의 복잡성 기능에 대한 지식의 실제 적용은 두 가지입니다. 첫째, 특정 작업에 대해 문헌에 관련 데이터가 있는 경우 보다 최적의 알고리즘을 선택할 수 있습니다. 둘째, 한 세트의 초기 데이터에 대한 해법의 실행 시간을 알면 학생은 주어진 문제에 대한 최대 제한 사항에 해당하는 데이터에 대해 동일한 프로그램의 실행 시간을 대략적으로 추정할 수 있습니다.