몽-구
몽구의 우당탕탕 개발 공부
몽-구
전체 방문자
오늘
어제
  • 분류 전체보기 (106)
    • PS (38)
      • 백준 (24)
      • 프로그래머스 (14)
    • Dev (58)
      • Kotlin (0)
      • Java (4)
      • Spring, SpringBoot (1)
      • C (8)
      • Python (10)
      • Dart (1)
      • 알고리즘 (7)
      • 자료구조 (3)
      • Git (1)
      • Linux (2)
      • VS Code (1)
      • 환경 설정 (8)
      • Conference (1)
      • 42Seoul (3)
      • Node.js (1)
      • ShellScript (1)
      • IntelliJ (0)
      • MacOS (2)
      • 기타 (3)
    • CS (1)
      • 데이터베이스 (1)
    • DS (4)
      • Coursera (4)
    • 리뷰 (1)
      • 제품 리뷰 (1)
    • 일상 (3)
      • 자동화 (1)
      • 목표 및 계획 (2)
      • 회고 (0)
    • 삶에 대한 태도 (1)
      • 유튜브를 보며 (1)

블로그 메뉴

  • GitHub

인기 글

반응형

태그

  • c언어
  • BOJ
  • sort
  • Linux
  • Python
  • 코딩테스트
  • 백준알고리즘
  • 리눅스
  • 백준온라인저지
  • Algorithm
  • 알고리즘
  • 파이썬
  • 프로그래머스
  • 정렬
  • 백준

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
몽-구

몽구의 우당탕탕 개발 공부

[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리
Dev/Python

[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리

2020. 4. 20. 19:18
반응형

파이썬으로 코딩테스트를 진행하며 가장 많이 쓰는 기본 자료형은 리스트(list)와 문자열(string), 딕셔너리(dictionary), 집합(set) 정도이다. 기본 자료형을 벗어난 것 중 많이 쓰는 것은 collections 모듈의 Counter와 deque 정도가 있겠고, 아주 가끔 itertools 모듈의 permutations 혹은 combinations 정도를 쓰는 것 같다(사실 이 둘은 시간복잡도가 터져버리기 때문에 거의 안 쓴다).

 

약간 난이도가 있는 코딩테스트 문제들은 항상 시간복잡도와 공간복잡도에 대한 제약이 주어진다. 특히 시간복잡도에 대한 제약은 아주 중요하며, 이를 고려하기 위해서는 이용하는 자료형의 메소드 별 시간 복잡도를 알고 있어야 한다. 그래서 이번 기회에 정리를 해볼까 한다. 우선 리스트와 딕셔너리, 집합에 관한 메소드들에 대해 각각의 글로 정리해보고, cheat sheet 느낌으로 정리된 것만 하나 더 포스팅할까 생각 중이다. 오늘은 리스트부터 정리해보자.

 

아래 표에서 사용하는 약자 혹은 용어에 대한 설명은 다음과 같다.

  • l : list의 약자로, 리스트를 의미한다. l1과 l2가 등장한다면 서로 다른 리스트를 의미한다.
  • i : index의 약자로, 리스트 내 특정 인덱스를 의미한다.
  • a, b : 특정 인덱스를 의미하는 임의의 알파벳으로, 특정 인덱스부터 특정 인덱스까지의 범위를 지정할 때 사용했다.
  • x : 하나의 요소(혹은 객체)다.
  • item : x와 마찬가지이며, 리스트 안에 있는 요소들을 순회할 때 각 요소를 지칭하기 위해 쓴 용어이다.
  • k : 임의의 양의 정수이다.
  • 시간 복잡도에서의 N : number의 약자로, 리스트 내 원소 개수이다.

 

메소드 혹은 연산 이름
(Method or Operation)
사용 예시 (Example) 시간 복잡도 (Time Complexity)
* Big-O Notation 기준
설명
Index l[i] O(1)  
Store (or Assignment) l[i] = x O(1) l[a:b] = [...] 의 시간 복잡도 : O(b-a)
* Slice의 시간 복잡도와 동일하다.
Length len(l) O(1)  
Append l.append(x) O(1)  
Pop l.pop() O(1)  
Clear l.clear()
O(1) l = [ ] 와 같다.
Slice l[a:b] O(b-a)  
Extend l1.extend(l2)
(= l1+l2)
O(len(l2))  
Construction (or Casting) list(iterable object) O(len(iterable object))  
Check l1 == l2
l1 != l2
O(N) 각 리스트의 모든 원소가 동일한 인덱스에  위치한지 linear하게 순회하며 확인함.
Insert l(i, x) O(N) 리스트의 i번째 인덱스에 x를 삽입하고, 기존 리스트의 [i:]를 모두 한 칸씩 뒤로 미뤄야 함.
Delete del l[i] O(N) 리스트의 i번째 인덱스에 위치한 원소를 삭제하고, 그 뒤의 원소를 모두 한 칸씩 앞으로 당겨야 함.
Containment x in l
x not in l
O(N) x가 리스트 안에 있는지 (혹은 없는지) 확인하기 위해 리스트를 linear하게 순회하며 확인함.
Copy l.copy()
( =  l[:])
O(N) 리스트 l에 있는 모든 원소를 카피하기 위해 리스트를 linear하게 순회함.
Remove l.remove(x) O(N) 리스트에 x가 존재하는지 0번째 인덱스부터  linear하게 순회하다가, 최초의 x가 발견되면 그것을 삭제하고 그 뒤의 요소들을 모두 한 칸씩 앞으로 당김. x가 없다고 하더라도 x를 찾기 위해 리스트의 끝까지 순회함.
Pop for specific element l.pop([i]) O(N) Delete와 동일한 원리이며, 그저 Store 기능이 추가된 것일 뿐임.
Extreme Value min(l)
max(l)
O(N) 리스트를 linear하게 순회하며 어떤 원소가 가장 작은지 (혹은 가장 큰지) 확인함.
Reverse l.reverse()
( = l[::-1])
O(N)  
Itertation for item in l:
...
O(N)  
Sort l.sort()
sorted(l)
O(N logN) Tim Sort 원리에 따라 O(N logN).
Multiply k*l O(k N)  

참고로 각 메소드에 대한 기능 설명은 아래의 링크를 참고하자. 본 글에서는 시간 복잡도에 대해 주안점을 두었기 때문에 각 메소드에 대한 기능 설명은 생략하도록 한다.

1. 점프 투 파이썬

2. 공식 문서 (1)

3. 공식 문서 (2)

 

 

 

Source : https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

반응형
저작자표시 (새창열림)

'Dev > Python' 카테고리의 다른 글

[파이썬/Python] 정규표현식 - 리스트 내 원소들 중 숫자만 필터링하기  (0) 2022.02.20
[파이썬/Python] Collections - Deque  (0) 2020.10.09
[파이썬/Python] for - else / while - else 활용  (0) 2020.03.12
[파이썬/Python] 리스트의 정렬 방법 - sort함수와 sorted함수  (0) 2020.03.11
[파이썬/Python] 순열과 조합 (Permutation and Combination)  (0) 2020.03.10
    'Dev/Python' 카테고리의 다른 글
    • [파이썬/Python] 정규표현식 - 리스트 내 원소들 중 숫자만 필터링하기
    • [파이썬/Python] Collections - Deque
    • [파이썬/Python] for - else / while - else 활용
    • [파이썬/Python] 리스트의 정렬 방법 - sort함수와 sorted함수
    몽-구
    몽-구
    소망보단 목표를, 생각보단 실천을

    티스토리툴바