다음 코드 스 니펫의 시간 복잡도는 무엇입니까? x는 전역 변수이고 "statement"는 O (n) 시간이 걸린다고 가정하십시오.

-8

코드를 스크린 샷으로 게시하지 마십시오. – Verv

코드를 이미지로 붙여 넣었습니까? 1 분 만에 응답 했습니까? – R2RT

8 * A (n/2)는 숫자 곱하기 O (1) 시간이 걸립니다. 그래서 상기 함수의 점화식은 A (n은) = 인 A (N/2) + O (N) 마스터 이것을 우리가 (N) A (N) = (θ)

2017-12-18 20:47:32 debaonline4u

질문을 한 후 1 분 만에 스스로 대답하는 이유는 무엇입니까? – Verv

방금 매우 독특한 질문을 발견했습니다. 그게 바로 내가 공유 한 이유입니다. 나중에 나는 그것이 일어나서는 안된다는 것을 깨달았다. 어쨌든 그냥 참고 일 뿐이야, 다시는 일어나지 않을거야. – debaonline4u

다른 사람들에게도 도움이된다면 질문을 게시하고 대답하는 것이 좋습니다. 이 질문은 누군가가 검색을 통해 도달 할 수 있을지 의심 스럽기 때문에 작성되었습니다. –

얻을한다 정리 해결 n = 64라고 가정합니다.

호 1 (N = 64) : 문 + A (N/2) = O (N) + O (A (N/2))
통화 2 (N/2 = 32) : O (n/4) = O (n/4) = O (n/4) = O (n) + O (A (n/4))
호출 3 O (n/16) = O (n/8)
호출 4 (n/8 = 8) (n/32 = 2) : 문 + A (n/32) = 0 (n/32 = 2) 64) = O (n) + O (A (n/64))
호 7 (N/64 = 1) : O (1)

복잡도 = O (N) 성명] × 로그 (N) recursivity]

결론 : O (n.log (n))

2017-12-18 20:57:01 Imabot

답변