n + 1^n-1 형태니 빅오 n 맞냐
n + 1^n-1 형태니 빅오 n 맞냐
간단한 시간복잡도 이거 답 맞는지좀
88(182.226)
2015-04-24 00:23
추천 0
n + 1^n-1 형태니 빅오 n 맞냐
댓글 11
다른 게시글
-
자기소스코드 출력하는 코드;;ㅋㅋㅋㅋ [1]과제도우미(1.217) | 15.04.24추천 0
-
이거 시간복잡도점 구해주셈 [19]88(182.226) | 15.04.23추천 0
-
엑셀잘하시는 분~~ [2]엑셀어려워(61.102) | 15.04.23추천 0
-
이거 자바코드좀 짜주세요. [1]프로그래밍(116.36) | 15.04.23추천 0
-
싸우기 전에 윈10 빌드 10061 패치는 받으셨는지...? [10]whatugonna..(sibal214) | 15.04.23추천 0
-
이거 일반항 어케되냐 [1]88(182.226) | 15.04.23추천 0
-
밑에 과제도우미 글 읽고 생각난 재미있는 퀴즈인데... [13]ㅅㅅㅅ(125.128) | 15.04.23추천 0
-
분위기가 무겁네여 [4]씨알메리(crmerry) | 15.04.23추천 0
-
cos, sin 함수 이거.. [9]과제도우미(1.217) | 15.04.23추천 0
-
여기서 제이쿼리 최고 고수가 누구냐 질문좀 [3]익명(103.10) | 15.04.23추천 0
재귀를 한번만 호출할 때: f(N). 두번 이상 호출할 때: (재귀 횟수)^{f(N)}
아니 근데 직접 유도해서 푸는 법을 알려주는 게 좋겠다.
봐봐. T(n) = 1 + T(n - 1) 인 거 동의? 여기서 1은 return하는데 드는 비용인 거고, T(n - 1)은 재귀 호출했으니 그 함수 호출에 대한 비용인 거지.
T(n - 1)은 또 1 + T(n - 2)니까. T(n) = 1 + 1 + T(n - 2)가 돼고, 재귀적으로 적용하면 T(n) = 1 * k + T(n - k) 라는 걸 알 수 있다.
곧, T(n) = 1 * (n - 1) + T(1) 이라는 거고. T(1)은 위에서 n <= 1 이라는 base case에 걸리므로 return만 하기 때문에 T(1) = 1임. 곧, T(n) = 1 * (n - 1) + 1 = n임. 따라서 O(N)이야.
T(n)=1+n+T(n-1) 여기서 +n어디로 사라짓는지 모르겟네요 ㅠ
T(n) = 1 * k + T(n - k) 여기까진 이해되는데 어케T(n) = 1 * (n - 1) + T(1) 가되는지 모르겟어요 ㅠ
T(n) = 1 + T(n-1) = 1 + 1 + T(n-2) = 1 + 1 + 1 + T(n-3) = ... = 1 * (n-1) + T(1) = 1 * (n-1) + 1 = n
k에 n - 1을 넣어봐.
T(n) = 1 * (n-1) + T(n - (n-1)) = 1 * (n-1) + T(1) 임.
아하 그래서 T(1)은 조건식땜에 1이고 결과적으러 빅오 n