다음과 같이 구성된 알고리즘의 점근 시간을 확인하려고했습니다.알고리즘의 실행 시간 결정
알고리즘 Alg-1과 Alg-2는 모두 입력으로 받아 들여 n 개의 항목이있는 배열을 생성합니다.
Δ1g의-1
ALG-1(A[1,...,n])
1: B= ALG-1(A[1,...,⎿n/2⏌])
2: C= ALG-2(A[⎿n/2⏌+1,...,n])
3: return ALG-2(B,C)
내가 ALG-2 시간 F (N)를 실행하는 Θ (√n) 인 것을 고려하면, ALG-1의 점근 실행 시간을 결정하려는 것이다.
알고리즘에 대한 반복을 작성한 다음 마스터 정리를 통해 해결하려고하지만 시작하는 방법조차 모릅니다. 누군가가 저를 조금 도와 주면 기쁠 것입니다.
n = 2^k의 입력에 ALG-1을 실행하는 데 걸리는 시간을 이라고합시다. ALG-2(B, C)은 과 C의 연결로 실행되는 ALG-2이고 길이는 n이라고 가정합니다. 당신이 재발 C는 상수
T_k = T_{k - 1} + sqrt(n/2) + sqrt(n) = T_{k - 1} + C * sqrt(2^k),
을 가지고있는 것처럼 그런 것 같습니다. 당신이 등, T_{k - 2}의 측면에서 T_{k - 1}를 작성하여 그것을 밖으로 확대 유지하는 경우, 당신은이 기하학적 시리즈, 그래서 합이 주요 용어 (기본적으로, 첫 번째 항과 같은 순서이다
T_k = C * sqrt(2^k) + C * sqrt(2^{k - 1}) + C * sqrt(2^{k - 2}) + ...
를 얻을 수 나머지 모든 용어의 합계만큼 크다). 따라서 T_k은 sqrt(2^k) 또는 sqrt(n)입니다.
답장을 보내 주셔서 감사합니다. 그러나 이제는 다소 혼란 스럽습니다. 우리는 배열을 두 개의 하위 배열로 나눠서 모든 n 개의 요소를 한 번에 통과하므로 T (n) = 2 (n/2) + n과 같이 재발이 sth처럼 보일 것이라고 생각했습니다. 어떻게 (k-1)을 얻습니까? –
당신은 ALG-2에 데이터를 전달할 때 알고리즘 자체가 O (sqrt (n)) 시간 만 걸리는 경우에도 O (n) 시간이 걸린다는 점에서 좋은 점을 알 수 있습니다. 크기 n 입력에 대해서만 O (log n) 시간 소요). 그러나 이는 일반적으로 데이터를 참조로 전달하여 전체 배열을 복사하는 대신 포인터를 전달하여 피할 수 있습니다. – arghbleargh
좋아요, 지금은 더 의미가 있다고 생각합니다. –