글 읽기 - 데크의 시간복잡도 계산

nh0903 2년 전 0

위의 코드로 계산시 python 기준 3000ms정도 걸리고 밑의 코드일시 약 100ms 정도 걸립니다.

제가 생각하기에 위의 코드의 시간복잡도는 lst의 크기인 O(N)과 K번 만큼의 반복이라서 시간복잡도 O(NK)라고 생각합니다.

밑의 코드의 시간 복잡도는 O(N) X idx의 크기(lst.pop(idx)이기 때문에)라고 생각하는데 맞는건가요?

밑의 코드가 위의 코드보다 빠른 이유는 idx의 최댓값이 N번 반복하는 동안 항상 -1(idx의 최댓값이 len(lst)인데 반복할수록 길이가 줄기때문)되기 때문에 위의 코드보다 빠르다고 생각하는데 맞는건가요?

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
lst = deque(list(range(1, n+1)))

result = []
while lst:
    for _ in range(k-1):
        lst.rotate(-1)
    result.append(str(lst.popleft()))

print("<"+', '.join(result)+">")

######################################

import sys
n, k = map(int, sys.stdin.readline().split())
lst = list(range(1, n+1))

result = []
idx = 0

for _ in range(n):
    idx += k - 1
    if idx >= len(lst):
        idx %= len(lst)
    result.append(str(lst.pop(idx)))

print("<" + ', '.join(result) +">")

djm03178 2년 전 1

반복할수록 길이가 줄어드는 건 위쪽 코드도 마찬가지입니다. 만약 거기서 차이가 있었다고 해도 횟수는 약 2배 차이만 나야 하는데 이건 30배가 납니다.

파이썬은 내장으로 구현된 기능과 파이썬 스크립트로 구현한 기능에 상상을 초월하는 성능 차이가 있습니다. 중간의 원소를 pop하는 것은 분명 시간 복잡도상으로는 매우 느린 작업이지만, 이 부분이 C로 짜여져 있고 그 중에서도 매우 단순한 연산을 수행하는 작업이기 때문에 상수에서 엄청나게 유리합니다.

nh0903 2년 전 0

답변해주셔서 감사합니다!! 제가 아직 C를 안배워서 이번 2학기때 배우게 되는데 그럼 더 자세히 알 수 있을거 같아요.

그럼 코드상으로는 둘다 O(NK)로 시간복잡도는 같다라고 봐야하는거지요?

djm03178 2년 전 0

네, 일반적인 방법으로 시뮬레이션을 하는 코드는 대체로 O(NK)가 됩니다.

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

문제

문제

출처

ICPC

데크의 시간복잡도 계산

nh0903 2년 전 0

djm03178 2년 전 1

nh0903 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말