알고리즘 분석

지정된 순서 목록에서 특정 엔트리를 조회하기 위해 이진 및 선형 검색 알고리즘(순서를 무시함)을 모두 사용할 수 있습니다.전자 알고리즘과 후자 알고리즘의 분석에 따르면

크기

n의 리스트에 대해 각각

최대 2

로그

n

과 n의 체크 단계를 거칩니다.표시된 크기 33의 예제 목록에서 "Morin, Arthur" 검색은 각각 2진수(시안 표시) 및 선형(마젠타) 검색과 함께 5단계 및 28단계로 이루어집니다.

알고리즘 분석에 일반적으로 사용되는 함수의 그래프. 각 함수의 입력

크기

n에 대한 연산 수를

나타냅니다

.

컴퓨터 과학에서 알고리즘 분석은 알고리즘의 계산 복잡성, 즉 알고리즘 실행에 필요한 시간, 스토리지 또는 기타 리소스를 찾는 프로세스입니다.통상, 알고리즘의 입력 사이즈와 스텝의 수(시간 복잡도) 또는 사용하는 스토리지 장소의 수(공간 복잡도)를 관련짓는 함수를 결정합니다.알고리즘은 이 함수의 값이 작거나 입력 크기의 증가에 비해 느리게 증가할 때 효율적이라고 한다.같은 사이즈의 입력이 다르면 알고리즘의 동작이 다를 수 있으므로, 베스트, 워스트, 및 평균의 케이스의 설명이 모두 실용적으로 도움이 됩니다.특별히 지정하지 않는 한 알고리즘의 성능을 기술하는 함수는 보통 알고리즘에 대한 최악의 입력에서 결정되는 상한입니다.

"알고리즘 분석"이라는 용어는 도널드 ^[1]크누스에 의해 만들어졌다.알고리즘 분석은 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공하는 광범위한 계산 복잡도 이론의 중요한 부분입니다.이러한 추정치를 통해 효율적인 알고리즘에 대한 합리적인 검색 방향을 파악할 수 있습니다.

알고리즘의 이론적 분석에서는 점근적 의미에서 알고리즘의 복잡성을 추정하는 것이 일반적이다. 즉, 임의적으로 큰 입력에 대한 복잡도 함수를 추정하는 것이다.이를 위해 Big O 표기법, Big-Omega 표기법 및 Big-theta 표기법이 사용됩니다.예를 들면, 바이너리 검색은, 검색 대상의 정렬 리스트의 $사이즈$ n의 대수에 비례하는 스텝수, 또는 O $(log$ n $)$ 에서는, 구어체로 「대수 시간」으로 실행한다고 한다.동일한 알고리즘의 구현에 따라 효율성이 다를 수 있기 때문에 일반적으로 점근 추정치가 사용됩니다.그러나 주어진 알고리즘의 두 가지 "합리적인" 구현의 효율성은 숨겨진 상수라고 불리는 상수 승수에 의해 관련됩니다.

때때로 정확한 (점근적이지 않은) 효율성 측정이 계산될 수 있지만, 일반적으로 계산 모델이라고 불리는 알고리즘의 특정 구현에 관한 특정 가정을 필요로 한다.계산 모델은 예를 들어 추상컴퓨터의 관점에서 정의할 수 있다.튜링 기계 및/또는 특정 연산이 단위 시간에 실행된다고 가정함으로써.예를 들어 바이너리 검색을 적용하는 정렬된 목록에 n개의 요소가 $있고$ 목록 내 요소의 각 룩업이 단위 시간으로 수행될 수 있는 경우 응답을 반환하려면 최대 $log (n$ ) + $1개$ 의₂ 시간 단위가 필요합니다.

비용 모델

시간 효율의 추정치는, 순서로서 정의되고 있는 것에 의해서 다릅니다.분석이 실제 런타임에 유용하게 대응하려면 단계를 수행하는 데 필요한 시간이 상수에 의해 위에서 제한되도록 보장해야 합니다.여기에는 주의해야 합니다. 예를 들어 일부 분석에서는 두 숫자의 추가를 한 단계로 간주합니다.이 가정은 특정 컨텍스트에서는 보증되지 않을 수 있습니다.예를 들어, 계산에 관련된 숫자가 임의로 클 경우, 단일 덧셈에 필요한 시간은 더 이상 일정하다고 가정할 수 없다.

일반적으로 다음 두 가지 비용 ^[2]^[3]^[4]^[5]^[6]모델이 사용됩니다.

균등 비용 측정(및 유사한 변동)이라고도 불리는 균등 비용 모델은 관련된 숫자의 크기에 관계없이 모든 기계 작동에 일정한 비용을 할당합니다.
로그 비용 측정이라고도 불리는 로그 비용 모델은 관련된 비트 수에 비례하는 모든 기계 작동에 비용을 할당합니다.

후자는 사용하기 번거롭기 때문에 암호화에 사용되는 알고리즘과 같은 임의 정밀도 산술 알고리즘의 분석 등 필요한 경우에만 사용합니다.

자주 간과되는 중요한 점은 문제의 하한이 실제로 사용할 수 있는 연산 세트보다 제한된 계산 모델에 대해 종종 주어지고, 따라서 순진하게 생각할 ^[7]수 있는 것보다 더 빠른 알고리즘이 있다는 것입니다.

런타임 분석

런타임 분석은 알고리즘의 입력 크기(보통 $n$ 으로 표시됨)가 증가함에 따라 실행 시간(또는 실행 시간 또는 실행 시간)의 증가를 예측하고 예측하는 이론적 분류입니다.런타임 효율은 컴퓨터 과학에서 큰 관심을 끄는 주제입니다.프로그램은 어떤 알고리즘을 구현하느냐에 따라 몇 초, 몇 시간 또는 몇 년이 걸릴 수 있습니다.소프트웨어 프로파일링 기술은 실제로 알고리즘의 런타임 측정에 사용할 수 있지만, 가능한 모든 입력에 대해 무한히 많은 타이밍 데이터를 제공할 수는 없습니다.후자는 런타임 분석의 이론적인 방법에 의해서만 달성할 수 있습니다.

경험적 지표의 단점

알고리즘은 플랫폼에 의존하지 않기 때문에(즉, 주어진 알고리즘은 임의의 운영체제를 실행하는 임의의 컴퓨터에서 임의의 프로그래밍 언어로 구현될 수 있다), 주어진 알고리즘 세트의 비교 성능을 측정하기 위해 경험적 접근법을 사용하는 것에는 추가적인 중대한 단점이 있다.

크기 n의 정렬된 목록에서 특정 항목을 검색하는 프로그램을 예로 들어 보겠습니다.이 프로그램이 선형 검색 알고리즘을 사용하여 최첨단 기계인 컴퓨터 A에 구현되고 이진 검색 알고리즘을 사용하여 훨씬 느린 컴퓨터 B에 구현되었다고 가정합니다.각각의 프로그램을 실행하고 있는2대의 컴퓨터에 대한 벤치마크 테스트는 다음과 같습니다.

n(목록 크기)	컴퓨터 A 런타임 (나노초 단위)	컴퓨터 B 런타임 (나노초 단위)
16	8	100,000
63	32	150,000
250	125	200,000
1,000	500	250,000

이러한 메트릭에 근거해, 컴퓨터 A가 컴퓨터 B의 알고리즘보다 효율이 훨씬 뛰어난 알고리즘을 실행하고 있다고 단언하는 것은 간단합니다.다만, 입력 리스트의 사이즈가 충분한 수치로 증가하면, 그 결론은 에러인 것이 극적으로 판명됩니다.

n(목록 크기)	컴퓨터 A 런타임 (나노초 단위)	컴퓨터 B 런타임 (나노초 단위)
16	8	100,000
63	32	150,000
250	125	200,000
1,000	500	250,000
...	...	...
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 10¹²	31,536 × 10¹² ns, 또는 1년	1,375,000 ns, 또는 1.375 밀리초

선형 검색 프로그램을 실행하는 컴퓨터 A는 선형 증가율을 나타냅니다.프로그램의 실행 시간은 입력 크기에 정비례합니다.입력 크기를 2배로 하면 실행 시간이 2배로 늘어나고 입력 크기가 4배로 증가하는 등 실행 시간이 4배로 증가합니다.반면 바이너리 검색 프로그램을 실행하는 컴퓨터 B는 로그 증가율을 보인다.입력 크기를 4배로 늘리면 실행 시간이 일정량만 증가합니다(이 예에서는 50,000ns).컴퓨터 A가 표면적으로는 더 빠른 머신이지만, 컴퓨터 B는 훨씬 느린 성장률로 알고리즘을 실행하고 있기 때문에 런타임에서 컴퓨터 A를 능가할 수밖에 없습니다.

성장순서

$비공식적$ 으로 알고리즘은 어떤 $입력$ 크기 n을 넘어 함수 f( $n)$ 곱하기 정의 상수가 그 알고리즘의 런타임에 상한 또는 한계를 제공하는 경우 수학 함수의 순서로 증가율을 나타낸다고 할 수 있다.즉, 특정 입력 $크기$ n이 $일부$ ₀ n보다 크고 $상수$ c에 대해 해당 알고리즘의 실행 시간은 c × $f (n)$ 보다 크지 않습니다.이 개념은 Big O 표기법을 사용하여 자주 표현됩니다.예를 들어 삽입 정렬의 런타임은 입력 사이즈가 커짐에 따라 2차적으로 증가하므로 삽입 정렬은 O $(n 2) 차라고$ 할 수 있다.

빅 O 표기법은 특정 알고리즘의 최악의 시나리오를 표현하는 편리한 방법입니다.단, 예를 들어 퀵소트의 최악의 시나리오는 $O$ $($ $n 2)$ 이지만 평균적인 케이스의 $런타임$ 은 $O$ ( $n$ log n $)$ 입니다.

경험적 성장 순서

실행 시간이 멱함수 $규칙$ t $µ a$ kn을 따른다고 가정하면, 계수 $a$ 는 일부 문제 크기 지점 { $n 1, n 2$ }에서 실행 시간 { $t 1, t 2$ }을 경험적으로 측정하고 a = $log(t 2 / t 1)/log(n 2 / n 1)$ 가 $되도록$ t $/ t 1 =(n 2 / n 1) a$ 를₂ 계산하여 구할 수 있습니다.즉, 이것은 특정 크기 지점에서 실행 시간 대 입력 크기의 로그-로그 그림에서 경험적 선의 기울기를 측정합니다.성장순서가 실제로 멱함수 규칙을 따른다면(따라서 로그-로그 그림의 선은 실제로 직선)의 경험값은 다른 범위에서 일정하게 유지되며, 그렇지 않으면 변화한다(그리고 선은 곡선이다). 그러나 여전히 성장순서에 대한 두 가지 주어진 알고리즘의 비교에 도움이 될 수 있다.에하비유어위 표에 적용됨:

n(목록 크기)	컴퓨터 A 런타임 (나노초 단위)	현지 성장 순서 (n^_)	컴퓨터 B 런타임 (나노초 단위)	현지 성장 순서 (n^_)
15	7		100,000
65	32	1.04	150,000	0.28
250	125	1.01	200,000	0.21
1,000	500	1.00	250,000	0.16
...	...		...
1,000,000	500,000	1.00	500,000	0.10
4,000,000	2,000,000	1.00	550,000	0.07
16,000,000	8,000,000	1.00	600,000	0.06
...	...		...

첫 번째 알고리즘은 멱함수 법칙에 따른 선형 성장 순서를 나타내는 것이 명백하다.두 번째 것의 경험적 가치는 빠르게 감소하고 있으며, 이는 또 다른 성장 규칙을 따르고 있으며, 어떤 경우에도 첫 번째 것보다 훨씬 낮은 성장 순서(그리고 더 나아짐)를 가지고 있음을 시사한다.

런타임 복잡성 평가

특정 알고리즘의 최악의 시나리오에 대한 런타임 복잡도는 알고리즘의 구조를 조사하고 몇 가지 간단한 가정을 함으로써 평가할 수 있습니다.다음의 의사 코드에 대해 검토합니다.

입력 2에서 양의 정수 n을 얻습니다. n > 10 3 인쇄 "이 작업은 시간이 좀 걸릴 수 있습니다." 4(i = 1~n 5(j = 1 ~i 6 인쇄 i * j 7 인쇄 "완료됨!")

주어진 컴퓨터는 이 알고리즘의 실행에 관련된 각 명령을 실행하는 데 이산적인 시간이 걸립니다.주어진 명령을 실행하는 구체적인 시간은 실행 중인 명령과 실행 중인 컴퓨터에 따라 다르지만, 기존 컴퓨터에서는 이 양이 ^[9]결정적일 수 있습니다.스텝 1에서 수행된 액션은 시간₁ T를 소비하는 것으로 간주되며 스텝2는 시간₂ T를 사용하는 것으로 간주됩니다.

위의 알고리즘에서는 스텝1, 2, 7은 1회만 실행됩니다.최악의 경우 3단계도 실행된다고 가정해야 합니다.따라서 스텝 1~3과 스텝7을 실행하는 총 시간은 다음과 같습니다.

{\displaystyle T_{1}+T_{2}+T_{3}+T_{7},

스텝 4, 5, 6의 루프는 평가하는 것이 더 까다롭습니다.스텝 4의 외부 루프테스트는 (n + 1)회 실행됩니다(for 루프를 종료하기 위해서는 추가 스텝이 필요하므로 n + 1이 아닌n의 실행이 필요합니다).이 테스트에는₄ T(n + 1)의 시간이 소요됩니다.반면 내부 루프는 1부터 i까지 반복되는 j 값에 의해 제어됩니다.외부 루프를 통과하는 첫 번째 패스에서는 j가 1부터1까지 반복됩니다.내부 루프가 1회 통과하기 때문에 내부 루프 본체(스텝 6)를 실행하면 T시간, 내부 루프 테스트(스텝 5)에는 2T시간이₅ 소요됩니다₆.외부 루프를 통과하는 다음 패스 중에 j는 1에서2까지 반복됩니다.내부 루프가 2회 통과하기 때문에 내부 루프 본체의 실행(스텝 6)에는 2T의₆ 시간이 소요되며, 내부 루프 테스트(스텝 5)에는 3T의₅ 시간이 소요됩니다.

전체적으로 내부 루프 본체를 실행하는 데 필요한 총 시간은 산술적 수열로 나타낼 수 있습니다.

T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6

로서^[10] 고려될 수 있다

\displaystyle \left [1+2+3+\cdots +(n-1)+n\right]T_{6}=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}:

외부 루프 테스트 실행에 필요한 총 시간도 동일하게 평가할 수 있습니다.

\displaystyle\signed\&2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}\=\&T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}\end{aligned}}

로서 고려될 수 있다

디스플레이 스타일T_{5}\left [1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}\\=&left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+nT_{5}\\=&left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end {aligned}}

따라서 이 알고리즘의 총 런타임은 다음과 같습니다.

{\displaystyle f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left [{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left [{\frac {1}{2}}(n^{2}+3n)\right]T_{5}:

즉, 으로 환원됩니다.

f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left [{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}

하나의 법칙으로서, 주어진 함수에서 가장 높은 차수의 항이 그 증가율을 지배하고 따라서 런타임 순서를 정의한다고 가정할 수 있다.이 예제에서 n은² 가장 높은 차수 항이므로 f $(n)$ = $O (n 2)$ 로 $결론$ 을 내릴 수 있습니다.이는 공식적으로 다음과 같이 입증될 수 있습니다.

$\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ ( $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ 2 $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ ) $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ ] $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + [ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ 2 ( $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ n $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ ) ] $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ 5 $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + ( $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ ) $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ 4 + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ 2 + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ , n $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$ 0 { $display$ \ $style$ \ left [ { \ $frac$ { \ { \ 2 $}$ { 2 + 3 $n }$ \ n } \ $n$ 오른쪽임을 증명합니다. $T_{6}+\left [{\frac {1}{2}}(n^{2}+3n)\right]$ $T_{5}+(n+1)$ $T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\n\geq n_{0}$

${\displaystyle {\frac {1}{2}}(n^{2}+n)\오른쪽]T_{6}+\left [{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\({\text{for }}n\geq 0)\end{aligned}}})$

k가 [T₁]보다 크거나 같은 상수라고 하자.T₇]

$디스플레이 스타일T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+kn(n^{2}+3n)+kn+kn\=&2kn^{2}+5kn^2}+kn2kn^2}+kn2kn2kn2+kn2kn2kn2kn2kn2kn2+kn2kn2kn2kn2kn2kn2+kn2kn2kn2kn2kn2kn2$

$\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ [ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 2 ( $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 2 + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ ) $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ ] $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 6 + [ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 2 ( $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ n $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ ) ] $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 5 + ( $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ ) $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 4 + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ + T $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 2 + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 3 + $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 7 $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ n $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 2 , $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ 、 $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ { $display$ style \ [ \ $frac {$ 2 $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$ } { $2$ } { $n$ } { n } $T_{6}+\left [{\frac {1}{2}}(n^{2}+3n)\right]$ $T_{5}+(n+1)$ $T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1}$

이 알고리즘을 분석하는 보다 우아한 방법은 [T₁]를 선언하는 것입니다.T]는₇ 모두 1단위의 시간 단위와 같으며, 1단위가 이들 스텝의 실제 시간보다 크거나 같도록 선택된 단위 시스템에서는 1단위는 모두 1단위와 같습니다.즉, 알고리즘의 런타임은 다음과 ^[11]같이 분류됩니다.

$({displaystyle 4+\sum _{i=1}^{n}\sum _{i=1}^{n=4+n^{2}\leq 5n^{2}\({\text{for }}n\geq 1)=O(n^{2}).}$

기타 자원의 증가율 분석

런타임 분석 방법은 메모리 공간 소비와 같은 다른 증가율을 예측하는 데도 사용할 수 있습니다.예를 들면, 다음의 의사 코드로, 그 프로그램이 관리하는 파일의 사이즈에 근거해, 프로그램 마다 메모리 사용량을 관리해, 재할당합니다.

파일이 아직 열려 있는 동안: n = 파일 크기가 100,000킬로바이트 증가할 때마다 예약된 메모리 양이 두 배로 증가합니다.

이 경우 파일사이즈 n이 커지면 메모리는 지수 증가율( $O (2))$ 로ⁿ 소비됩니다.이는 메모리 자원의 소비량이 매우 빠르고 관리하기 어려운 증가율입니다.

연계

비효율적인 알고리즘을 우발적으로 또는 의도하지 않게 사용하면 시스템퍼포먼스에 큰 영향을 줄 수 있기 때문에 알고리즘 분석은 실제로 중요합니다.시간에 민감한 응용 프로그램에서는 알고리즘 실행에 시간이 너무 오래 걸리면 결과가 오래되거나 무용지물이 될 수 있습니다.비효율적인 알고리즘은 실행하는데 비경제적인 컴퓨팅 능력이나 스토리지가 필요하게 되어 사실상 무용지물이 될 수도 있습니다.

상수 요인

알고리즘의 분석은 일반적으로 점근 성능에 초점을 맞추지만, 실제 적용에서는 일정한 요인이 중요하며 실제 데이터는 항상 크기가 제한된다.제한은 일반적으로 주소 지정 가능한 메모리의 크기이므로 32비트 머신에서는³² 2 = 4 GiB(세그먼트메모리를 사용하는 경우 최대) 및 64비트 머신에서는⁶⁴ 2 = 16 EiB입니다.따라서 제한된 크기가 주어지면 성장 순서(시간 또는 공간)를 상수 인자로 대체할 수 있으며, 이러한 의미에서 모든 실용적인 알고리즘은 충분히 큰 상수 또는 충분히 작은 데이터에 대해 O( $1)$ 가 $됩니다$ .

이 해석은 (2진수) 반복 로그(로그^*)는 모든 실제 데이터(2비트)에서⁶⁵⁵³⁶ 5 미만, (2진수) 로그 로그(로그 n)는 거의 모든 실제 데이터(2비트⁶⁴)에서 6 미만, 이진 로그(로그 n)는 거의 모든 실제 데이터(2비트⁶⁴)에서 64 미만 등 매우 느리게 증가하는 함수에 주로 유용합니다.만약 일정 시간 알고리즘 결과의 더 큰 일정한 요소, 예를 들어의 오버 헤드, 한 K사용할 수 있non-constant 복잡성을 받으며 그럼에도 불구하고 더 지속적인 복잡성에 실질적인 데이터에 대한 알고리즘보다 k 로그 ⁡ 로그⁡ n{\displaystyle K>, k\log\log n}한 K/k>6{\displaystyl 효율적일 수 있다.eK/k> 6} $K/k>6$ $n<2^{2^{6}}=2^{64}$ n $n<2^{2^{6}}=2^{64}$ < $n<2^{2^{6}}=2^{64}$ $n<2^{2^{6}}=2^{64}$ 6 $=$ $n<2^{2^{6}}=2^{64}$ $n<2^{2^{6}}=2^{64}$ { $display n$ < $2$ ^ { 2 $n<2^{2^{6}}=2^{64}$ ^ { 6 } = 2 $n<2^{2^{6}}=2^{64}$ ^ { $64$ } 。

큰 데이터 선형 또는 2차 요인의 경우 무시할 수 없지만 작은 데이터의 경우 점근적으로 비효율적인 알고리즘이 더 효율적일 수 있습니다.이는 특히 Timsort와 같은 하이브리드 알고리즘에서 사용됩니다.Timsort는 점근적으로 효율적인 알고리즘(여기서는 시간 $n\log n$ $n\log n$ n $n\log n$ \ $displaystyle$ n $\log$ $n\log n$ n $)$ 을 사용하지만 작은 데이터에는 점근적으로 비효율적인 알고리즘(여기서는 시간 $n^{2}$ 2 \ $n^{2}$ n $^{2$ 으로 전환합니다.더 간단한 알고리즘은 작은 데이터에서도 더 빠릅니다.

「」를 참조해 주세요.

메모들

^ "Knuth: Recent News". 28 August 2016. Archived from the original on 28 August 2016.
^ 섹션Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co. ISBN 9780201000290. 1.3
^ Juraj Hromkovič (2004). Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. pp. 177–178. ISBN 978-3-540-14015-3.
^ Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. pp. 3–8. ISBN 978-3-540-65431-5.
^ Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, p. 20, ISBN 978-3-540-21045-0
^ Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. pp. 3–7. ISBN 978-0-89871-187-5.
^ 추상화 가격의 예? cstheory.stackexchange.com
^ 2017-03-08년 Wayback Machine에서 아카이브된 O-Ause와 Blute를 피하는 방법(Gödel's Lost Letter and P=NP) 조지아 공대 컴퓨터 공학 교수 R. J. Lipton의 블로그 "Gödel's Lost Letter and P=NP"에서 Robert Sedgewick의 아이디어를 다시 소개합니다.
^ 그러나 양자 컴퓨터에서는 그렇지 않습니다.
^ 1 $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + ( $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ n - $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ) + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ( $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ) $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ( \ $displaystyle 1$ + 2 + 3 + \ $cdots$ + ( n - $1$ ) + $n = scdots$ { $n$ ( n + 1 ) } { 2 } $that$ that that that that that that by by it it it it it it it it it it it it it it it it it it it it it it it it it it it it1 + 2 ? $}}}$
^ 위의 접근법과 달리 이 접근법은 각각의 루프를 종료하는 루프 테스트에 소비되는 일정한 시간을 무시하지만 그러한 누락이 최종 결과에 영향을 미치지 않음을 증명하는 것은 사소한 일이다.

레퍼런스

Sedgewick, Robert; Flajolet, Philippe (2013). An Introduction to the Analysis of Algorithms (2nd ed.). Addison-Wesley. ISBN 978-0-321-90575-8.
Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser. ISBN 3-7643-3102-X.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2001). Introduction to Algorithms. Chapter 1: Foundations (Second ed.). Cambridge, MA: MIT Press and McGraw-Hill. pp. 3–122. ISBN 0-262-03293-7.
Sedgewick, Robert (1998). Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6.
Knuth, Donald. The Art of Computer Programming. Addison-Wesley.
Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0.

외부 링크

Wikimedia Commons 알고리즘 분석 관련 매체

[1] "Knuth: Recent News". 28 August 2016. Archived from the original on 28 August 2016.

[AhoHopcroft1974-2] 섹션Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co. ISBN 9780201000290. 1.3

[Hromkovič2004-3] Juraj Hromkovič (2004). Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. pp. 177–178. ISBN 978-3-540-14015-3.

[Ausiello1999-4] Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. pp. 3–8. ISBN 978-3-540-65431-5.

[Wegener20-5] Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, p. 20, ISBN 978-3-540-21045-0

[Tarjan1983-6] Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. pp. 3–7. ISBN 978-0-89871-187-5.

[7] 추상화 가격의 예? cstheory.stackexchange.com

[8] 2017-03-08년 Wayback Machine에서 아카이브된 O-Ause와 Blute를 피하는 방법(Gödel's Lost Letter and P=NP) 조지아 공대 컴퓨터 공학 교수 R. J. Lipton의 블로그 "Gödel's Lost Letter and P=NP"에서 Robert Sedgewick의 아이디어를 다시 소개합니다.

[9] 그러나 양자 컴퓨터에서는 그렇지 않습니다.

[10] 1 $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + ( $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ n - $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ) + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ( $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ + $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ) $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$ ( \ $displaystyle 1$ + 2 + 3 + \ $cdots$ + ( n - $1$ ) + $n = scdots$ { $n$ ( n + 1 ) } { 2 } $that$ that that that that that that by by it it it it it it it it it it it it it it it it it it it it it it it it it it it it1 + 2 ? $}}}$

[11] 위의 접근법과 달리 이 접근법은 각각의 루프를 종료하는 루프 테스트에 소비되는 일정한 시간을 무시하지만 그러한 누락이 최종 결과에 영향을 미치지 않음을 증명하는 것은 사소한 일이다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[10]

[11]

v t 컴퓨터 공학
주의: 이 템플릿은 대략 2012 ACM Computing Classification System에 준거하고 있습니다.
하드웨어	프린트 기판 주변기기 집적회로 대규모 통합 시스템온칩(SoC) 소비전력(친환경 컴퓨팅) 전자 설계 자동화 하드웨어 액셀러레이션
컴퓨터 시스템 구성	컴퓨터 아키텍처 임베디드 시스템 실시간 컴퓨팅 신뢰성
네트워크	네트워크 아키텍처 네트워크 프로토콜 네트워크 컴포넌트 네트워크 스케줄러 네트워크 퍼포먼스 평가 네트워크 서비스
소프트웨어 구성	통역사 미들웨어 가상 머신 운영 체제 소프트웨어 품질
소프트웨어 표기법 및 도구	프로그래밍 패러다임 프로그래밍 언어 컴파일러 도메인 고유의 언어 모델링 언어 소프트웨어 프레임워크 통합 개발 환경 소프트웨어 형상 관리 소프트웨어 라이브러리 소프트웨어 저장소
소프트웨어 개발	제어 변수 소프트웨어 개발 프로세스 요건 분석 소프트웨어 설계 소프트웨어 구축 소프트웨어 도입 소프트웨어 엔지니어링 소프트웨어 유지보수 프로그래밍팀 오픈 소스 모델
계산 이론	계산 모형 격식어 오토마타 이론 계산가능성 이론 계산 복잡도 이론 논리 의미론
알고리즘	알고리즘 설계 알고리즘 분석 알고리즘 효율 랜덤화 알고리즘 계산기하학
컴퓨팅의 수학	이산 수학 확률 통계 정보 수학 소프트웨어 정보 이론 수학적 해석 수치 분석 이론 컴퓨터 공학
정보 시스템	데이터베이스 관리 시스템 정보 스토리지 시스템 엔터프라이즈 정보 시스템 소셜 정보 시스템 지리정보시스템 의사결정지원시스템 공정관리시스템 멀티미디어 정보 시스템 데이터 마이닝 디지털 라이브러리 컴퓨팅 플랫폼 디지털 마케팅 월드 와이드 웹 정보 검색
보안.	암호화 형식적인 방법 보안 서비스 침입 탐지 시스템 하드웨어 보안 네트워크 보안 정보 보안 응용 프로그램 보안
인간과 컴퓨터의 상호 작용	상호작용 설계 소셜 컴퓨팅 유비쿼터스 컴퓨팅 시각화 접근성
동시성	동시 컴퓨팅 병렬 컴퓨팅 분산 컴퓨팅 멀티스레딩 멀티프로세서
인공지능	자연어 처리 지식 표현 및 추론 컴퓨터 비전 계획 및 스케줄링 자동화 검색 방법론 제어방법 인공지능의 철학 분산형 인공지능
기계 학습	지도 학습 비지도 학습 강화 학습 멀티태스킹 학습 교차 검증
그래픽스	애니매이션 렌더링 이미지 조작 그래픽스 처리 장치 혼합현실 가상현실 이미지 압축 솔리드 모델링
응용 컴퓨팅	전자상거래 엔터프라이즈 소프트웨어 계산 수학 계산물리학 계산화학 계산생물학 계산사회과학 계산공학 컴퓨터 헬스케어 디지털 아트 전자 출판 사이버 전쟁 전자투표 비디오 게임 워드프로세서 운용 조사 교육용 테크놀로지 문서 관리
카테고리 개요 위키프로젝트 공통

Search

알고리즘 분석

네임스페이스

더

목차

비용 모델