이 질문은 비교적 간단 해 보이지만 n의 관점에서 실행 시간을 찾을 수없는 것 같습니다.
문제는 다음과 같습니다.
j = n;
while(j >= 2) {
j = j^(1/2)
}
총 실행 시간은 필요하지 않습니다. 두 번째와 세 번째 줄이 맞는 횟수를 계산하는 방법 만 알면됩니다 (동일해야 함). 나는 이것을 찾는 데 어떤 종류의 공식이 있는지 알고 싶습니다. 위의 내용이 다음과 동일하다는 것을 알 수 있습니다.
for(j = n; n >= 2; j = j^(1/2)
작업 유형은 중요하지 않으며 라인이 실행될 때마다 1 시간 단위로 계산됩니다. 따라서 1 행은 1 시간 단위이고 2 행은 다음과 같습니다.
도움을 제공하는 모든 사람에게 미리 감사드립니다! 대단히 감사합니다!
거꾸로 작업하여 2 행의 시간 단위 수를 구하십시오.
time
n n log_2(n) units
1 1 0 0
2 2 1 1
4 4 2 2
16 16 4 3
16^2 256 8 4
(16^2)^2 65536 16 5
((16^2)^2)^2) ... 32 6
즉, 시간 단위의 수에 대해 t, n2 ^ (2 ^ (t-1)) 인 경우를 제외하고 t = 0있는 경우 n = 1.
이것을 되돌리려면
n <2 일 때 t = 0
t = 로그 2 (로그 2 (n)) + 1 (n> = 2 인 경우)
여기서 로그 2 (x)는 x의 이진 로그 로 알려져 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다