[파이썬][리스트] 리스트 연산의 시간 복잡도 예제

22 Aug 2023

python

리스트 연산의 시간 복잡도는 해당 연산이 리스트의 크기에 어떻게 영향을 미치는지를 나타내는 개념입니다. 시간 복잡도는 보통 빅 오 표기법으로 표현되며, 이를 통해 연산의 성능을 예측하고 비교할 수 있습니다. 아래 예제를 통해 몇 가지 리스트 연산의 시간 복잡도를 살펴보겠습니다.

def example_operations(n):
    # 리스트 생성 (O(n))
    my_list = list(range(n))
    
    # 리스트에 원소 추가 (O(1))
    my_list.append(n+1)
    
    # 리스트의 첫 번째 원소 접근 (O(1))
    first_element = my_list[0]
    
    # 리스트의 마지막 원소 접근 (O(1))
    last_element = my_list[-1]
    
    # 리스트에서 특정 원소 검색 (O(n))
    index_of_element = my_list.index(n // 2)
    
    # 리스트의 모든 원소 출력 (O(n))
    for element in my_list:
        print(element)
    
    # 리스트의 원소를 정렬 (O(n log n))
    sorted_list = sorted(my_list)
    
    # 리스트의 원소를 병합 (O(n))
    merged_list = my_list + my_list
    
    # 리스트의 원소 개수 확인 (O(1))
    length = len(my_list)

위의 예제에서 n은 리스트의 크기입니다. 각 연산의 시간 복잡도는 주석에 주석으로 표시되어 있습니다. 리스트 생성, 원소 추가, 원소 접근 등은 대부분 O(1)의 시간 복잡도를 가지지만, 리스트의 원소를 검색하거나 정렬하는 작업은 O(n)이거나 O(n log n)의 시간 복잡도를 가집니다.

시간 복잡도 개념을 통해 어떤 연산이 어떤 크기의 리스트에 대해 얼마나 빠르게 실행될지 예측하고, 연산 성능을 최적화하는 데 도움이 됩니다.