혹시 시간복잡도 아시는 분 계신가요?
귀염포텐
2023.04.01
j = n
while ( j = 1){
for i = 1 to j
x = x + 1
j = j/2
}
while문에서 어떻게 계산해야 될지 모르겠네요ㅜ 아시는 분 상세하게 좀 가르쳐 주시면 감사하겠습니다ㅜ
p.s 답은 세타(n)이라네요.
-
알렉산더
마법의손님.. ┗j/2 ┛ - 양 옆에 이거 의미가 무엇인지 아세요?
-
텐시
아..감사합니다~
-
애기
j가 N이면......for()문이... 1~N까지 작동하죠.....끝난후..... J는 N/2가 됩니다.......
그래서 for()는 다시 1~N/2까지 작동하구요..... 끝나면 J는 N/4가 됩니다....
... 그래서 for()가 작동하는 횟수를 보면... N + N/2 + N/4 + N/8 + N/16 ..... 이렇게 됩니다...
N( 1 + 1/2 + 1/4 + ..... ) 등비수열의 합을 보시면 되구요...... :).... -
벚꽃
계산 방법 좀 가르쳐주실 수 있나요?
-
빵순
네..... O(N)이네요...~~ 정확히는.... 2N(1-(0.5)^N) 인데... N이 충분히 크면.. 2N이고... 고로.....O(N)이죠..