글 읽기 - python 시간복잡도 관련 질문입니다

yklee1130 3년 전 0

#1 코드와 같이 리스트의 인덱스 값을 증가시키며 비교 병합 시에는 통과하지만

#2 코드와 같이 리스트의 크기를 줄여가며 비교 병합 시에는 시간 초과가 발생합니다.

pop이나 슬라이싱이 시간이 더 드는 이유가 궁금합니다!

#1
def merge(front, rear):
    new = []
    l =0
    r = 0
    while len(front) > l and len(rear) > r:
        if front[l] < rear[r]:
            new.append(front[l])
            l += 1
        else:
            new.append(rear[r])
            r += 1
    new += rear[r:]
    new += front[l:]
    return new


#2
def merge(front, rear):
    new = []
    while len(front) != 0 and len(rear) != 0:
        if front[0] < rear[0]:
            new.append(front.pop(0))
        else:
            new.append(rear.pop(0))
    new += rear
    new += front
    return new

ysc7064 3년 전 2

pop(0) 의 시간복잡도는 O(len(list))입니다.

pop(0) 를 해야한다면,

1. deque 의 popleft 메서드를 쓰거나,

2. list 를 반전시켜(reversed) pop() 하여 꼬리를 자르는 것이 좋습니다. (둘다 O(1))

#1 코드의 경우 list slicing 한다 하더라도, 시간복잡도는 O(n) 일거 같네요

#2 코드의 경우 매번 2 * O(n) + 2* O(n-1) ... 결국 n^2 입니다.

yklee1130 3년 전 0

아 이해됐어요! 감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

python 시간복잡도 관련 질문입니다

yklee1130 3년 전 0

ysc7064 3년 전 2

yklee1130 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말