알고리즘 효율성

컴퓨터 과학에서 알고리즘 효율성(algorithmic efficiency)은 알고리즘이 사용하는 연산 자원의 양과 관련된 속성이다. 알고리즘 효율성은 반복적이거나 지속적인 프로세스에 대한 엔지니어링 생산성에 비유될 수 있다.

최대 효율성을 위해서는 자원 사용량을 최소화하는 것이 바람직하다. 그러나 시간 및 공간 복잡성과 같은 다른 자원은 직접 비교할 수 없으므로, 두 알고리즘 중 어느 것이 더 효율적인지로 간주될지는 종종 어떤 효율성 척도가 가장 중요한지에 따라 달라진다.

예를 들어, 사이클 정렬과 팀소트는 모두 항목 목록을 가장 작은 것부터 가장 큰 것까지 정렬하는 알고리즘이다. 사이클 정렬은 항목 수의 제곱에 비례하는 시간(${\textstyle O(n^{2})}$, 점근 표기법 참조)으로 목록을 정리하지만, 원본 배열에 대한 쓰기 횟수를 최소화하고 목록 길이에 대해 상수인(${\textstyle O(1)}$) 적은 양의 추가 주기억장치만 필요로 한다. 팀소트는 목록 길이의 선형로그 시간(수량에 로그를 곱한 값에 비례)으로 목록을 정렬하지만(${\textstyle O(n\log n)}$), 목록 길이의 선형적인 공간 요구 사항을 가진다(${\textstyle O(n)}$). 특정 응용 프로그램에서 대용량 목록을 고속으로 정렬해야 하는 경우 팀소트가 더 나은 선택이다. 그러나 정렬의 프로그램/삭제 주기와 메모리 풋프린트를 최소화하는 것이 더 중요하다면 사이클 정렬이 더 나은 선택이다.

배경

시간에 대한 효율성의 중요성은 에이다 러브레이스가 1843년에 찰스 배비지의 기계식 해석 기관에 적용하면서 강조했다.

"거의 모든 계산에서 프로세스 연속을 위한 다양한 배열이 가능하며, 계산 엔진의 목적에 따라 그 중에서 선택에 영향을 미치는 다양한 고려 사항이 있어야 한다. 필수적인 목표 중 하나는 계산 완료에 필요한 시간을 최소화하는 경향이 있는 배열을 선택하는 것이다."^[1]

초기 전자 컴퓨터는 속도와 랜덤 액세스 메모리가 모두 제한적이었다. 따라서 시공간 트레이드오프가 발생했다. 태스크는 많은 메모리를 사용하는 빠른 알고리즘을 사용하거나, 적은 메모리를 사용하는 느린 알고리즘을 사용할 수 있었다. 따라서 엔지니어링 트레이드오프는 사용 가능한 메모리에 맞는 가장 빠른 알고리즘을 사용하는 것이었다.

현대 컴퓨터는 초기 컴퓨터보다 훨씬 빠르고 훨씬 더 많은 메모리를 사용할 수 있다(킬로바이트 대신 기가바이트). 그럼에도 불구하고 도널드 커누스는 효율성이 여전히 중요한 고려 사항임을 강조했다.

"기존의 공학 분야에서는 쉽게 얻을 수 있는 12%의 개선조차 결코 한계로 간주되지 않으며, 소프트웨어 공학에서도 동일한 관점이 적용되어야 한다고 생각한다."^[2]

AI 시대에는 LLM이 작동하는 코드를 생성할 수 있지만, 이러한 코드는 자원 제약적이거나 시간에 민감한 애플리케이션에서 요구되는 성능 표준에 미치지 못하는 경우가 많아^[3] 실제 배포를 위한 코드 효율성이 중요한 병목 현상이 된다.

개요

알고리즘은 자원 소비(연산 비용이라고도 함)가 허용 가능한 수준이거나 그 이하일 때 효율적이라고 간주된다. 대략적으로 말해 '허용 가능'하다는 것은 일반적으로 입력 크기의 함수로서 사용 가능한 컴퓨터에서 합리적인 시간이나 공간 내에 실행될 것임을 의미한다. 1950년대 이후 컴퓨터는 사용 가능한 연산 능력과 메모리 양 모두에서 극적인 증가를 보였으므로, 현재 허용 가능한 수준은 불과 10년 전에는 허용되지 않았을 것이다. 사실, 컴퓨터 성능이 약 2년마다 두 배로 증가한 덕분에, 현대 스마트폰과 임베디드 시스템에서 허용 가능한 수준의 효율성을 보이는 작업도 10년 전에는 산업용 서버에서 허용할 수 없을 정도로 비효율적이었을 수 있다.

컴퓨터 제조업체는 종종 더 높은 성능을 가진 새로운 모델을 출시한다. 소프트웨어 비용은 상당히 높을 수 있으므로, 어떤 경우에는 더 높은 성능을 얻는 가장 간단하고 저렴한 방법은 기존 컴퓨터와 호환되는 한 더 빠른 컴퓨터를 구매하는 것일 수 있다.

알고리즘이 사용하는 자원을 측정하는 방법은 여러 가지가 있다. 가장 일반적인 두 가지 측정값은 속도와 메모리 사용량이다. 다른 측정값으로는 전송 속도, 임시 디스크 사용량, 장기 디스크 사용량, 전력 소비량, 총소유비용, 외부 자극에 대한 응답 시간, 등이 있을 수 있다. 이러한 측정값 중 다수는 알고리즘 입력의 크기, 즉 처리할 데이터의 양에 따라 달라진다. 또한 데이터가 배열되는 방식에 따라 달라질 수도 있다. 예를 들어, 일부 정렬 알고리즘은 이미 정렬되어 있거나 역순으로 정렬된 데이터에서 성능이 좋지 않다.

실제로 정확도와 정밀도 및 신뢰성에 대한 요구 사항과 같이 알고리즘의 효율성에 영향을 미칠 수 있는 다른 요소가 있다. 아래에서 자세히 설명하겠지만, 알고리즘이 구현되는 방식도 실제 효율성에 상당한 영향을 미칠 수 있지만, 이 중 많은 측면은 최적화 문제와 관련이 있다.

이론적 분석

이론적인 알고리즘 분석에서는 일반적으로 점근적 의미에서 복잡도를 추정한다. 자원 소비 또는 "복잡도"를 설명하는 데 가장 일반적으로 사용되는 표기법은 도널드 커누스의 점근 표기법으로, 입력 크기 ${\textstyle n}$의 함수로 알고리즘의 복잡도를 나타낸다. 점근 표기법은 함수의 복잡도에 대한 점근적 측정치이며, ${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$는 대략적으로 알고리즘의 시간 요구 사항이 ${\displaystyle g(n)}$에 비례하며, ${\textstyle n}$이 무한히 커질 때 함수의 증가에 ${\displaystyle g(n)}$보다 적게 기여하는 하위 차수 항을 생략한다는 의미이다. 이 추정치는 ${\textstyle n}$이 작을 때 오해의 소지가 있을 수 있지만, 표기법이 점근적이므로 ${\textstyle n}$이 클 때는 일반적으로 충분히 정확하다. 예를 들어, 버블 정렬은 몇 개의 항목만 정렬할 때는 합병 정렬보다 빠를 수 있다. 그러나 두 구현 모두 작은 목록에 대한 성능 요구 사항을 충족할 가능성이 있다. 일반적으로 프로그래머는 대규모 입력 크기에 효율적으로 확장되는 알고리즘에 관심이 있으며, 대부분의 데이터 집약적인 프로그램에서 접하는 길이의 목록에는 버블 정렬보다 합병 정렬이 선호된다.

알고리즘의 점근적 시간 복잡도에 적용되는 점근 표기법의 몇 가지 예는 다음과 같다.

표기법	이름	예시
${\displaystyle O(1)}$	상수	측정값의 정렬된 목록에서 중앙값 찾기; 고정 크기 순람표 사용; 항목 조회를 위해 적절한 해시 함수 사용.
${\displaystyle O(\log n)}$	로그	이진 탐색 또는 균형 잡힌 검색 트리를 사용하여 정렬된 배열에서 항목 찾기, 그리고 이항 힙의 모든 연산.
${\displaystyle O(n)}$	선형	정렬되지 않은 목록 또는 잘못 형성된 트리(최악의 경우) 또는 정렬되지 않은 배열에서 항목 찾기; 리플 캐리로 두 n비트 정수 더하기.
${\displaystyle O(n\log n)}$	선형로그, 로그선형 또는 유사선형	고속 푸리에 변환 수행; 힙 정렬, 퀵 정렬 (최선 및 평균의 경우), 또는 합병 정렬
${\displaystyle O(n^{2})}$	제곱	단순 알고리즘으로 두 n자리 숫자 곱하기; 버블 정렬 (최악의 경우 또는 순진한 구현), 셸 정렬, 퀵 정렬 (최악의 경우), 선택 정렬 또는 삽입 정렬
${\displaystyle O(c^{n}),\;c>1}$	지수	동적 계획법을 사용하여 외판원 문제의 최적 (비근사) 해 찾기; 무차별 대입 검색을 사용하여 두 논리 문이 동등한지 확인하기

성능 측정

새로운 버전의 소프트웨어 또는 경쟁 시스템과의 비교를 위해 때때로 벤치마크가 사용되며, 이는 알고리즘의 상대적 성능을 측정하는 데 도움이 된다. 예를 들어, 새로운 정렬 알고리즘이 생성되면 기존 데이터에서 이전과 같이 효율적인지 확인하기 위해 이전 버전과 비교할 수 있으며, 기능 개선 사항을 고려한다. 벤치마크는 고객이 기능 및 성능 측면에서 특정 요구 사항에 가장 적합한 제품을 추정하기 위해 대체 공급업체의 다양한 제품을 비교할 때 사용할 수 있다. 예를 들어, 메인프레임 세계에서 Syncsort와 같은 독립 소프트웨어 회사의 특정 독점 정렬 제품은 IBM과 같은 주요 공급업체의 제품과 속도 면에서 경쟁한다.

일부 벤치마크는 예를 들어 다양한 컴파일 언어와 해석 언어의 상대적 속도를 비교하는 분석을 생성할 기회를 제공한다^[4][5] 그리고 컴퓨터 언어 벤치마크 게임은 여러 프로그래밍 언어에서 일반적인 프로그래밍 문제 구현의 성능을 비교한다.

심지어 "DIY" 벤치마크를 만드는 것도 다양한 사용자 지정 기준을 사용하여 다른 프로그래밍 언어의 상대적 성능을 보여줄 수 있다. 이는 크리스토퍼 W. 카우웰-샤(Christopher W. Cowell-Shah)의 "9개 언어 성능 라운드업"이 예시로 보여주듯이 매우 간단하다.^[6]

구현 관련 고려 사항

구현 문제 또한 효율성에 영향을 미칠 수 있는데, 예를 들어 프로그래밍 언어의 선택, 알고리즘이 실제로 코드화되는 방식,^[7] 특정 언어를 위한 컴파일러의 선택, 사용된 컴파일러 옵션, 심지어 사용 중인 운영체제 등이다. 많은 경우 인터프리터로 구현된 언어는 컴파일러로 구현된 언어보다 훨씬 느릴 수 있다.^[4] JIT 컴파일과 인터프리트 언어에 대한 문서를 참조하라.

시간 또는 공간 문제에 영향을 미칠 수 있지만 프로그래머의 통제 범위를 벗어날 수 있는 다른 요인들도 있다. 여기에는 데이터 정렬, 데이터 세분성, 캐시 국부성, 캐시 일관성, 쓰레기 수집, 명령어 수준 병렬성, 멀티스레딩 (하드웨어 또는 소프트웨어 수준에서), 동시 멀티스레딩, 서브루틴 호출 등이 포함된다.^[8]

일부 프로세서에는 벡터 처리 기능이 있어 단일 명령어로 여러 피연산자를 처리할 수 있다. 프로그래머나 컴파일러가 이러한 기능을 사용하기 쉬울 수도 있고 그렇지 않을 수도 있다. 순차 처리를 위해 설계된 알고리즘은 병렬 처리를 사용하기 위해 완전히 재설계해야 할 수도 있고, 쉽게 재구성할 수도 있다. 2010년대 후반에 병렬 및 분산 컴퓨팅의 중요성이 커짐에 따라, CUDA, 텐서플로, 아파치 하둡, OpenMP, MPI와 같은 병렬 및 분산 컴퓨팅 시스템을 위한 효율적인 고급 API에 대한 투자가 증가하고 있다.

프로그래밍에서 발생할 수 있는 또 다른 문제는 동일한 명령어 집합(예: X86-64 또는 ARM)과 호환되는 프로세서가 명령어를 다른 방식으로 구현할 수 있으므로, 일부 모델에서는 상대적으로 빠른 명령어가 다른 모델에서는 상대적으로 느릴 수 있다는 것이다. 이는 종종 최적화 컴파일러에게 어려움을 준다. 최적화 컴파일러는 성능을 위해 프로그램을 최적으로 최적화하려면 컴파일 대상의 특정 CPU 및 기타 하드웨어에 대한 광범위한 지식을 가지고 있어야 한다. 극단적인 경우, 컴파일러는 컴파일 대상 플랫폼에서 지원되지 않는 명령어를 에뮬레이션해야 할 수 있으며, 그 플랫폼에서는 계산할 수 없는 결과를 생성하기 위해 코드를 생성하거나 외부 라이브러리 호출을 링크해야 할 수 있다. 이는 다른 플랫폼에서는 기본적으로 지원되고 하드웨어에서 더 효율적일지라도 마찬가지이다. 이는 임베디드 시스템에서 부동소수점과 관련하여 자주 발생하는데, 작고 저전력 마이크로컨트롤러는 종종 부동소수점 연산에 대한 하드웨어 지원이 부족하여 부동소수점 계산을 생성하기 위해 계산 비용이 많이 드는 소프트웨어 루틴이 필요하기 때문이다.

자원 사용 측정

측정값은 일반적으로 입력 크기 ${\displaystyle \scriptstyle {n}}$의 함수로 표현된다.

가장 일반적인 두 가지 측정값은 다음과 같다.

• 시간: 알고리즘이 완료되는 데 얼마나 걸리는가?
• 공간: 알고리즘에 필요한 작업 메모리(일반적으로 RAM)는 얼마나 되는가? 여기에는 두 가지 측면이 있다. 코드에 필요한 메모리 양(보조 공간 사용량)과 코드가 작동하는 데이터에 필요한 메모리 양(고유 공간 사용량)이다.

배터리 전원으로 작동하는 컴퓨터(예: 랩톱 및 스마트폰) 또는 매우 길거나 큰 계산(예: 슈퍼컴퓨터)의 경우 관심 있는 다른 측정값은 다음과 같다.

• 직접 전력 소비: 컴퓨터 작동에 직접 필요한 전력.
• 간접 전력 소비: 냉각, 조명 등에 필요한 전력.

2018년 기준^[update], 전력 소비는 임베디드 사물인터넷 장치에서 시스템 온 칩 장치, 서버 팜에 이르기까지 모든 유형과 규모의 계산 작업에 대한 중요한 측정 지표로 성장하고 있다. 이러한 추세는 종종 그린 컴퓨팅으로 언급된다.

덜 일반적인 계산 효율성 측정값도 일부 경우에 관련될 수 있다.

• 전송 크기: 대역폭이 제한 요인이 될 수 있다. 데이터 압축을 사용하여 전송할 데이터 양을 줄일 수 있다. 그림이나 이미지(예: Google 로고)를 표시하면 "Google"이라는 텍스트 6바이트 전송과 비교하여 수만 바이트(이 경우 48K)가 전송될 수 있다. 이는 I/O 바운드 컴퓨팅 작업에 중요하다.
• 외부 공간: 디스크 또는 기타 외부 메모리 장치에 필요한 공간. 이는 알고리즘이 실행되는 동안 임시 저장 공간일 수도 있고, 나중에 참조하기 위해 장기 저장 공간일 수도 있다.
• 응답 시간(레이턴시): 실시간 응용 프로그램에서 컴퓨터 시스템이 외부 이벤트에 빠르게 응답해야 할 때 특히 관련이 있다.
• 총소유비용: 특히 컴퓨터가 특정 알고리즘에 전념하는 경우.

시간

이론

일반적으로 시간 복잡도와 같은 개념을 사용하는 알고리즘 분석을 사용하여 입력 데이터 크기의 함수로 실행 시간을 추정할 수 있다. 결과는 일반적으로 점근 표기법을 사용하여 표현된다. 이는 알고리즘을 비교하는 데 유용하며, 특히 많은 양의 데이터를 처리해야 할 때 유용하다. 데이터 양이 적을 때는 알고리즘 성능을 비교하기 위해 더 자세한 추정치가 필요하지만, 이는 중요성이 떨어질 가능성이 높다. 병렬 알고리즘은 분석하기가 더 어려울 수 있다.

실제

벤치마크는 실제로 알고리즘의 성능을 평가하는 데 사용될 수 있다. 많은 프로그래밍 언어에는 CPU 타임 사용량을 제공하는 함수가 있다. 오래 실행되는 알고리즘의 경우 경과 시간도 중요할 수 있다. 결과는 일반적으로 여러 테스트를 통해 평균화되어야 한다.

실행 기반 프로파일링은 하드웨어 구성과 다중 처리 및 다중 프로그래밍 환경에서 동시에 실행되는 다른 프로그램 또는 작업의 가능성에 매우 민감할 수 있다.

이러한 종류의 테스트는 특정 프로그래밍 언어, 컴파일러 및 컴파일러 옵션의 선택에도 크게 의존하므로, 비교되는 알고리즘은 모두 동일한 조건에서 구현되어야 한다.

공간

이 섹션은 알고리즘이 실행되는 동안 메모리 리소스(레지스터, 캐시, RAM, 가상 메모리, 보조 메모리) 사용에 관한 것이다. 위에서 언급한 시간 분석과 마찬가지로, 알고리즘 분석을 수행하고 일반적으로 공간 복잡도 분석을 사용하여 입력 데이터 크기의 함수로 필요한 실행 시간 메모리를 추정한다. 결과는 일반적으로 점근 표기법을 사용하여 표현된다.

고려해야 할 메모리 사용량 측면은 최대 4가지가 있다.

• 알고리즘 코드를 저장하는 데 필요한 메모리 양.
• 입력 데이터에 필요한 메모리 양.
• 출력 데이터에 필요한 메모리 양.
  • 정렬과 같은 일부 알고리즘은 종종 입력 데이터를 재배열하며 출력 데이터에 추가 공간이 필요하지 않다. 이 속성을 "제자리" 작업이라고 한다.
• 계산 중 작업 공간으로 필요한 메모리 양.
  • 여기에는 지역 변수와 계산 중에 호출되는 루틴에 필요한 스택 공간이 포함된다. 이 스택 공간은 재귀 기술을 사용하는 알고리즘에 상당할 수 있다.

초기 전자 컴퓨터와 초기 가정용 컴퓨터는 작업 메모리 양이 상대적으로 적었다. 예를 들어, 1949년 EDSAC은 최대 1024개의 17비트 워드 작업 메모리를 가졌고, 1980년 신클레어 ZX80은 초기에는 1024개의 8비트 바이트 작업 메모리를 가졌다. 2010년대 후반에는 개인용 컴퓨터가 일반적으로 4에서 32 GB의 RAM을 가지며, 이는 3억 배 이상 증가한 메모리 양이다.

캐싱과 메모리 계층

 메모리 계층 구조 문서에 이 부분의 추가 정보가 있습니다.

현대 컴퓨터는 상대적으로 많은 양의 메모리(기가바이트 단위)를 가질 수 있으므로, 알고리즘을 제한된 양의 메모리에 맞춰야 하는 문제는 예전과 같지 않다. 그러나 다양한 유형의 메모리와 상대적인 접근 속도는 중요하다.

• 프로세서 레지스터는 가장 빠르고 공간이 가장 적은 메모리이다. 현대 컴퓨터에서 대부분의 직접적인 계산은 필요한 경우 캐시, 주 메모리 및 가상 메모리로 업데이트되기 전에 레지스터의 원본 및 대상 피연산자로 발생한다. CPU 코어에는 일반적으로 수백 바이트 이하의 레지스터 가용성이 있지만, 레지스터 파일은 명령어 집합 아키텍처에 정의된 레지스터보다 더 많은 물리적 레지스터를 포함할 수 있다.
• 캐시 메모리는 메모리 계층 구조에서 두 번째로 빠르고 두 번째로 작은 메모리이다. 캐시는 CPU 또는 GPU와 같은 프로세서에 존재하며, 일반적으로 정적 RAM으로 구현되지만 디스크 드라이브와 같은 주변 장치에서도 발견될 수 있다. 프로세서 캐시는 종종 자체 다단계 계층 구조를 가진다. 하위 수준은 더 크고 느리며 일반적으로 멀티 코어 프로세서에서 프로세서 코어 간에 공유된다. 캐시 메모리에서 피연산자를 처리하려면 프로세서는 캐시에서 데이터를 가져와 레지스터에서 작업을 수행하고 데이터를 캐시에 다시 기록해야 한다. 이 작업은 L1 캐시에 있는 경우 CPU 또는 GPU의 산술 논리 장치 또는 부동소수점 장치와 비슷한 속도(약 2-10배 느림)로 작동한다.^[9] L1 캐시 미스가 발생하여 L2 캐시에서 데이터를 가져오고 기록해야 하는 경우 약 10배 더 느려지며, L2 캐시 미스가 발생하여 L3 캐시에서 데이터를 가져와야 하는 경우(있는 경우) 다시 10배 더 느려진다.
• 주 물리적 메모리는 대부분 동적 RAM (DRAM)으로 구현된다. 주 메모리는 L3 CPU 캐시보다 훨씬 크고(일반적으로 ≈8 메가바이트에 비해 기가바이트 단위) 읽기 및 쓰기 지연 시간이 일반적으로 10-100배 더 느리다.^[9] 2018년 기준^[update], RAM은 CPU 또는 그래픽 처리 장치 메모리와 같이 프로세서의 온칩으로 점점 더 많이 구현되고 있다.
• 가상 메모리 관리에 자주 사용되는 페이징된 메모리는 하드 디스크와 같은 보조 기억 장치에 저장되는 메모리로, 메모리 계층 구조의 확장으로 잠재적으로 더 큰 저장 공간을 사용할 수 있지만, 램의 값에 대한 캐시 미스보다 약 1000배 정도 더 높은 지연 시간이라는 비용이 따른다.^[9] 원래는 실제로 사용 가능한 메모리 양보다 더 많은 메모리가 있는 것처럼 보이게 하려는 의도로 개발되었지만, 가상 메모리는 시공간 트레이드오프와 가상 머신 사용을 가능하게 한다는 점에서 현대적으로 더 중요하다.^[9] 주 메모리에서 발생하는 캐시 미스는 페이지 부재라고 하며, 프로그램에 막대한 성능 저하를 초래한다.

메모리 요구 사항이 캐시 메모리에 맞는 알고리즘은 주 메모리에 맞는 알고리즘보다 훨씬 빠르며, 이는 페이징에 의존해야 하는 알고리즘보다 훨씬 더 빠르다. 이 때문에 캐시 교체 정책은 고성능 컴퓨팅에 매우 중요하며, 캐시 인식 프로그래밍과 데이터 정렬도 마찬가지이다. 문제를 더욱 복잡하게 만드는 것은 일부 시스템에는 다양한 실제 속도를 가진 최대 3단계의 캐시 메모리가 있다는 것이다. 시스템마다 이러한 다양한 유형의 메모리 양이 다르므로 알고리즘 메모리 요구 사항의 효과는 시스템마다 크게 다를 수 있다.

초기 전자 컴퓨팅 시대에는 알고리즘과 데이터가 주 메모리에 맞지 않으면 알고리즘을 사용할 수 없었다. 오늘날 가상 메모리의 사용은 훨씬 더 많은 메모리를 제공하는 것처럼 보이지만, 성능 저하가 따른다. 알고리즘과 데이터가 캐시 메모리에 맞는다면 훨씬 더 빠른 속도를 얻을 수 있으며, 이 경우 공간을 최소화하는 것이 시간 최소화에도 도움이 된다. 이를 국소성의 원리라고 하며, 참조 국부성, 공간적 국부성, 시간적 국부성으로 세분화할 수 있다. 캐시 메모리에 완전히 맞지 않더라도 참조 국부성을 보이는 알고리즘은 합리적으로 잘 수행될 수 있다.

같이 보기

• 알고리즘 분석 — 알고리즘에 필요한 자원을 결정하는 방법.
• 벤치마크 — 정의된 사례에서 비교 실행 시간과 공간을 측정하는 방법.^[10][11][12]
• 최선, 최악, 그리고 평균의 경우 — 세 가지 시나리오에서 실행 시간 추정을 위한 고려 사항.
• 컴파일러 최적화 — 컴파일러에서 파생된 최적화.
• 계산 복잡도 이론
• 컴퓨터 성능 — 컴퓨터 하드웨어 메트릭.
• 경험적 알고리즘론 — 알고리즘의 동작을 연구하기 위해 경험적 방법을 사용하는 관행.
• 프로그램 최적화
• 성능 분석 — 런타임에 알고리즘의 실제 성능을 측정하는 방법.