파이썬 내장 함수와 메소드의 시간 복잡도

 

파이썬은 다양한 내장 함수와 메소드를 제공하여 프로그래밍을 더 간편하게 만들어줍니다.

하지만 이러한 함수와 메소드의 실행 속도는 입력 크기에 따라 달라질 수 있습니다.

이 포스트에서는 주요 파이썬 내장 함수와 메소드의 시간 복잡도를 살펴보겠습니다.

1. 내장 함수의 시간 복잡도

type()

print(type([7, 5, 2, 3, 6])) # => <class 'list'>
print(type(5))               # => <class 'int'>
print(type(3.14))            # => <class 'float'>
print(type(True))            # => <class 'bool'>
print(type("True"))          # => <class 'str'>

type() 함수는 파라미터로 받은 값의 자료형을 반환합니다.

자료형은 파이썬 내부에서 고정된 값으로 저장되기 때문에 입력 크기에 영향을 받지 않습니다.

따라서 type() 함수의 시간 복잡도는 O(1)입니다.

max()와 min()

print(max(2, 5))             # => 5
print(max(2, 7, 5))          # => 7
print(min(2, 5))             # => 2
print(min(2, 7, 5, 11, 6))   # => 2

max() 함수는 주어진 값들 중에서 가장 큰 값을 반환하고, min() 함수는 가장 작은 값을 반환합니다.

두 함수는 파라미터 개수에 제한이 없으며, 각 파라미터를 비교하면서 결과를 찾기 때문에 시간 복잡도는 O(n)입니다.

여기서 n은 비교할 값의 개수입니다.

str()

my_str = str(257138)
print(my_str)                # => '257138'
print(type(my_str))          # => <class 'str'>

str() 함수는 숫자형 데이터를 문자열로 변환합니다.

숫자의 자릿수에 따라 변환 작업이 다소 달라질 수 있으며, 숫자의 자릿수를 d라고 할 때 시간 복잡도는 O(d)로, 대체로 O(log n)로 표현할 수 있습니다.

여기서 n은 숫자의 크기입니다.

2. 리스트 메소드의 시간 복잡도

append()

my_list = [7, 5, 2, 3, 6]
my_list.append(9)            # 리스트의 끝에 9 추가
print(my_list)               # => [7, 5, 2, 3, 6, 9]

append() 메소드는 리스트의 끝에 요소를 추가합니다. 이 작업은 상수 시간에 수행되므로 시간 복잡도는 O(1)입니다.

insert()

my_list.insert(2, 11)        # 2번 인덱스에 11 추가
print(my_list)               # => [7, 5, 11, 2, 3, 6, 9]

insert() 메소드는 지정된 인덱스에 요소를 추가합니다. 리스트의 요소를 이동해야 하기 때문에 시간 복잡도는 O(n)입니다. 여기서 n은 리스트의 길이입니다.

del

del my_list[2]               # 2번 인덱스의 값 삭제
print(my_list)               # => [7, 5, 2, 3, 6, 9]

del 키워드를 사용하여 리스트의 요소를 삭제합니다. 삭제 후 남은 요소를 이동해야 하므로 시간 복잡도는 O(n)입니다.

index()

my_index = my_list.index(9)  # my_list에서 9의 인덱스
print(my_index)              # => 5

index() 메소드는 리스트에서 특정 요소의 인덱스를 찾습니다.

요소를 처음부터 끝까지 검색해야 하므로 시간 복잡도는 O(n)입니다.

reverse()

my_list.reverse()            # 리스트 거꾸로 뒤집기
print(my_list)               # => [9, 6, 3, 2, 5, 7]

reverse() 메소드는 리스트의 요소 순서를 반대로 뒤집습니다.

모든 요소를 한 번씩 접근하므로 시간 복잡도는 O(n)입니다.

3. 정렬 메소드와 함수

sort()와 sorted()

my_list = [7, 5, 2, 3, 6]
print(sorted(my_list))       # => [2, 3, 5, 6, 7]
print(my_list)               # => [7, 5, 2, 3, 6]

my_list.sort()
print(my_list)               # => [2, 3, 5, 6, 7]

sort() 메소드는 리스트 자체를 정렬하고, sorted() 함수는 정렬된 새로운 리스트를 반환합니다.

두 함수는 모두 Timsort 알고리즘을 사용하며, 시간 복잡도는 O(n log n)입니다.

4. 리스트 슬라이싱

my_list = [7, 5, 2, 3, 6]
print(my_list[1:4])          # => [5, 2, 3]
print(my_list[:4])           # => [7, 5, 2, 3]
print(my_list[1:])           # => [5, 2, 3, 6]
print(my_list[:])            # => [7, 5, 2, 3, 6]
print(my_list[::2])          # => [7, 2, 6]

리스트 슬라이싱은 리스트의 부분을 추출하는 작업입니다.

슬라이싱의 시간 복잡도는 슬라이싱 범위의 길이에 비례하므로, 최악의 경우에는 O(n)입니다. 여기서 n은 슬라이싱 범위의 길이입니다.

5. len()

my_list = [7, 5, 2, 3, 6]
my_dict = {'a': 2, 'b': 3, 'c': 5, 'd': 7}
my_string = 'hello world'

print(len(my_list))          # => 5
print(len(my_dict))          # => 4
print(len(my_string))        # => 11

len() 함수는 리스트, 딕셔너리, 문자열 등의 길이를 반환합니다.

파이썬은 내부적으로 길이를 저장하므로, len() 함수는 이 정보를 직접 가져오는 작업만 수행하기 때문에 시간 복잡도는 O(1)입니다.

 

이 포스트가 파이썬의 주요 내장 함수와 메소드의 시간 복잡도를 이해하는 데 도움이 되길 바랍니다!

효율적인 코드를 작성하는 데 있어 이러한 시간 복잡도 개념은 매우 중요합니다.

공감과 댓글은 저에게 큰 힘이 됩니다.

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱