2012-04-24 1 views
0

주어진 함수에 의해 설정된 비용으로 프로세스의 알고리즘 복잡성을 결정해야하는 경우, O (n^2 log n) - 또는 큰 오우가 어찌 됐든간에?f (n) 비용을 사용한 연산의 알고리즘 복잡성

또한 큰 것은 아닐까요? 다항식에서 어떤 용어의 가장 높은 순서일까요? 파생물을 제공하라는 요청을 받으면 약간의 사소한 것으로 보여서 제공 할 항목이 확실하지 않습니다.

마지막 질문, 나는 알고리즘의 동작 수를 줄 필요하고 정말 간단합니다 경우 - 약 '작업 수'에 대한

array1, array2, array3 of size n 
for i in n: 
    array2[i] = sqrt(array1[i]) 
    array3[i] = array1[i]^2 

처럼 난 그냥 내 모든 산술 연산을 계산하고 파악 생각하는 같은 것들 (sqrt 같은) 여러 작업 등으로 계산 ... 아니면 그냥 O (n)이라고 쓸 수 있습니까?

답변

0

프로세스의 알고리즘 비용은 프로세스의 모든 구성 요소 비용입니다. 예를 들어, 예를 사용하여, 우리는 O (N)에있는이 각각의 어레이에 대한 n 개의 모든 시간이 소요 비용

array1, array2, array3 of size n 

, 3N 시간 정도로 전체를 분해 할 수있다.

for i in n: 

이것은 루프의 모든 항목에 n을 곱한 것을 의미합니다.

array2[i] = sqrt(array1[i]) 

이것은 O (1) 시간이 걸립니다. 왜? 배열 요소에 액세스하는 것은 일정한 시간입니다. sqrt를 가져 오는 것은 일정한 시간입니다. 그리고 배열 요소의 값을 설정하는 것은 일정한 시간입니다. 그래서 전체 작업은 일정한 시간입니다.

array3[i] = array1[i]^2 

이전 작업과 동일한 이유로 O (1) 시간이 걸립니다.

따라서 전체 실행 시간은 O (n) 시간 인 3n + n * (1 + 1)입니다. 그게 도움이 되니?

실제 파생에 관해서는 이에 대한 특정 기술이 있습니다. 빅 오 표기법의 정확한 수학적 정의를 배웠습니까?

This link은 big-Oh 표기법의 공식 정의를 설명하고이 내용을 증명하는 방법의 예를 제공합니다.

+0

저는 "array1, array2, array3 size n"을 입력으로 사용합니다. –

+0

오. 그렇다면, 그것은 중요하지 않습니다. 그러나 그것은 여전히 ​​O (n) 시간에있을 것입니다. – moowiz2020