Daily Temperatures 시간복잡도 질문

input = [73,74,75,71,69,72,76,73]
cnt =0
cntarr=[0] * len(input)
for x in range(len(input)):
    for y in range(x+1, len(input)):
        cnt +=1
        if input[y] > input[x]:
            cntarr[x] = cnt
            cnt=0
            break
        else:
            continue
    else :
        cnt=0
        cntarr[x] = cnt
print(cntarr)

문제에 대해서 위와같이 풀었을때

(1)

input = [73,74,75,71,69,72,76,73]

cntarr=[0] * len(input)

리스트 넣는 시간복잡도가 O(n)

(2)

for x in range(len(input)):
    for y in range(x+1, len(input)):

이중반복문 시간복잡도가 (n-1)! 이니까 O(n)

(3)

if input[y] > input[x]:

리스트의 요소 비교의 시간 복잡도가 O(1)

첫 번째 질문으로 이 식의 시간복잡도가 O(n) 인것이 맞는지 궁금합니다.

두 번째는

for x in range(len(input)):
    for y in range(x+1, len(input)):

위와 같은 이중반복문도 완전탐색이라고 하는 지 궁금합니다.

답변주시면 정말 감사하겠습니다.

# O(n^2)
def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for cur_day in range(n):
        for future_day in range(cur_day + 1, n):
            if temperatures[future_day] > temperatures[cur_day]:
                answer[cur_day] = future_day - cur_day
                break
    return answer

# O(n)
def dailyTemperatures(temperatures):
    ans = [0] * len(temperatures)
    stack = []
    for cur_day, cur_temp in enumerate(temperatures):
        while stack and stack[-1][1] < cur_temp:
            prev_day, _ = stack.pop()
            ans[prev_day] = cur_day - prev_day
        stack.append((cur_day, cur_temp))
    return ans

저는 코드를 위와 같이 작성했습니다. (디스코드 링크)

코먹하님의 코드에대한 시간복잡도를 보면,

(1) 네, 맞습니다.

(3) 네, 맞습니다.

(2) 이중반복문 시간복잡도가 (n-1)! 이니까 O(n) => 이게 무슨뜻일까요??

일단 이중 반복문에 대한 시간복잡도를 계산하기 위해서는 실행횟수를 계산해보는게 좋습니다. (보통 이중반복문을 O(n^2)이라고 생각하는데, 코드에 따라서 이중반복문이라도 O(n)도 될 수 있고, O(n^2)도 될 수 있습니다. )

만약 코드가 다음과 같다면 어떨까요

for i in range(n):
    for j in range(n):

O(n^2)이겠죠 (실행횟수가 n^2번 이니까)

만약 코드가 다음과 같다면 어떨까요

for i in range(n):
    for j in range(i+1, n):

이 때는 실행횟수가 어떻게 되냐면

(n-1) + (n-2) + (n-3) + ... 3 + 2 + 1 = n(n-1)/2 번 실행이 됩니다.

즉 (n^2 - n)/2 이니까, O(n^2)과 같겠죠.

즉 코먹하님의 코드

for x in range(len(input)):
    for y in range(x+1, len(input)):

의 시간복잡도가 O(n^2)이라서

전체 코드의 시간복잡도도 O(n^2)가 됩니다.

두 번째 질문

네, 완전탐색이라고 합니다.

완전탐색은 말 그대로 모든 경우의수를 탐색한다고 생각하시면 돼요.

보통 완전탐색은 재귀 또는 반복문으로 구현됩니다.

이중반복문이라서 완전탐색이다! 이건 아니고,

코먹하님의 코드가 모든 경우의수를 다 해보고 있다면 그건 완전탐색이 맞습니다.

질문에 대한 답이 됐을까요??

또 궁금하신점 있으면 얼만든지 질문주세요

인프런 커뮤니티 질문&답변