시간복잡도

: 파이썬에서 시간 복잡도는 알고리즘이나 프로그램이 어떤 문제를 해결하는데 필요한 시간이 입력 크기에 따라 어떻게 변하는지를 나타내는 척도다. 시간 복잡도는 일반적으로 빅 오 표기법(Big O notation)을 사용하여 표현된다. 이 표기법은 최악의 경우에서 알고리즘이나 함수가 얼마나 많은 연산을 수행해야 하는지를 나타낸다.

예를 들어:

• O(1): 상수 시간 복잡도. 입력 크기와 상관없이 항상 일정한 시간이 걸린다.

예시) 리스트의 특정 인덱스에 접근하는 경우

arr = [1, 2, 3, 4, 5]
print(arr[0])  

• O(n): 선형 시간 복잡도. 입력 크기에 비례하여 시간이 증가한다.

예시) 리스트의 모든 요소를 한번씩 확인하는 경우

for element in arr:
    print(element)  

• O(n^2): 이차 시간 복잡도. 입력 크기의 제곱에 비례하여 시간이 증가한다.

예시) 이중 반복문을 사용하는 경우

for i in arr:
    for j in arr:
        print(i,j)

• O(log n): 로그 시간 복잡도. 입력 크기가 커질수록 시간이 로그함수적으로 증가한다.

예시) 이진 탐색

def binary_search(arr,targe):
    left,right = 0, len(arr) - 1
    while left <= right:
      mid = (left+right) // 2
      if arr[mid] == tarhe

시간 복잡도는 알고리즘의 효율성을 판단하는 중요한 기준이며, 특히 큰 데이터셋을 다룰 때 더 중요하다. 좋은 알고리즘은 일반적으로 낮은 시간 복잡도를 가지며, 이는 더 적은 계산으로 더 빠른 결과를 얻을 수 있음을 의미한다.