데이터 구조 와 알고리즘 (1): 복잡 도 분석

데이터 구조 와 알고리즘 (1): 복잡 도 분석
최근 에 왕 쟁 선생님 의 을 배우 기 시 작 했 고 정 리 를 통 해 자신의 사고 형식 으로 이 과정 을 기록 했다. 글 은 주로 학습 과정의 기록 으로 삼 았 다.넓 은 의미 에서 볼 때 데이터 구 조 는 한 조 의 데이터 저장 구 조 를 말 하고 알고리즘 은 데 이 터 를 조작 하 는 한 조 의 방법 이다.알고리즘 복잡 도 는 시간 복잡 도와 공간 복잡 도로 나 뉘 는데 알고리즘 복잡 도 를 계산 할 때 보통 큰 O 기 호 를 사용한다.
시간 복잡 도
모든 코드 실행 시간 T (n) = O (f (n)). 그 중에서 f (n) 는 줄 마다 코드 가 실 행 된 횟수 를 합 친 것 을 나타 내 고 O 는 T (n) 는 f (n) 표현 식 과 정비례 하 며 n 은 보통 데이터 의 규 모 를 나타 낸다.

① def cal(n):
②    sum = 0
③    i =1
④    for j in range(n):
⑤        sum += 1
⑥    return sum

위의 절 차 를 예 로 들 면 ②, ③ 모두 한 번 실 행 했 고 ④, ⑤ 모두 n 번 실 행 했 기 때문에 T (n) = O (2n + 2) = O (n)
다음은 시간 복잡 도 분석의 세 가지 방법 을 말씀 드 리 겠 습 니 다.
1. 알고리즘 과 코드 시간 복잡 도 를 분석 할 때 순환 실행 횟수 가 가장 많은 코드 에 만 관심 을 가 져 야 한다. 위의 프로그램 을 예 로 들 면 n 이 많 을 때 10000, 100000 이 라 고 상상 할 수 있다. 공식 중의 낮은 단계, 상수 와 계수 가 성장 추 세 를 좌우 하지 않 고 무시 할 수 있 기 때문에 상기 문제 의 시간 복잡 도 는 O (n) 이다.또 예 를 들 어 5 n 4 + 3 n 3 + 2 n 2 + 4 n + 1 5n ^ 4 + 3 n ^ 3 + 2 n ^ 2 + 4 n + 1 5n4 + 3 n3 + 2n2 + 4n + 1 의 복잡 도 는 O (n ^ 4) 이다.
2. 덧셈 법칙: 총 복잡 도 는 헤비급 이 가장 큰 그 코드 의 복잡 도 와 같 습 니 다. 예 를 들 어 T1 (n) = O (f (n), T2 (n) = O (g (n), 그러면 T (n) = T1 (n) + T2 (n) = max (O (f (n), O (g (n) = O (max (f (n), g (n)))) = O (max (f (n), g (n)))))))))
3. 곱셈 법칙: 끼 워 넣 는 코드 의 복잡 도 는 끼 워 넣 는 내외 코드 의 복잡 도의 곱셈 과 같다.
몇 가지 흔히 볼 수 있 는 복잡 도 는 (낮은 단계 에서 높 은 단계 까지) (1), O (logn), O (n), O (nlogn), O (n 2 n ^ 2 n2) 가 있다.
1. O(1)

i,j = 1,2
sum = i+j

2. O(logn)

def fn(n):
    i = 1
    while(i<=n):
        i *= 2

시간 복잡 도 는 O (log ⁡ 2n \ \ log 2n log 2 n) 이 고 i * = 3 이면 O (l o g 3 n log 3n log 3 n) 이다.
3. O(n)

def fn(n):
    sum = 0
    for i in range(n):
        sum += 1

4. O(nlogn)

def fn(n):
    sum = 0
    for i in range(n):
        j = 1
        sum += 1
        while(j<=n):
            j *= 2

시간 복잡 도 O (  n l o g 2 n \ nlog_2n  nlog2​n)
5. O( n 2 n^2 n2)

def fn(n):
    sum = 0 
    for i in range(n):
        for j in range(n):
            sum += 1

시간 복잡 도 를 계속 분석 하고 네 가지 개념 을 도입 했다. 가장 좋 은 상황 시간 복잡 도, 최 악의 상황 시간 복잡 도, 평균 상황 시간 복잡 도, 평균 분담 시간 복잡 도.

def find(array,x):
    a =len(array)
    flag = -1
    for i in range(a):
        if array[i]==x:
            flag = i
            break
    return flag

위의 이 문 제 를 예 로 들 면 가장 좋 은 상황 의 복잡 도 는 x 가 배열 의 첫 번 째 요소 이다. 첫 번 째 변 수 를 찾 으 면 순환 이 종료 되 고 복잡 도 는 O (1) 이 며 가장 나 쁜 상황 의 복잡 도 는 x 가 배열 에 없 으 며 이때 복잡 도 는 O (n) 이다.다음은 평균 상황 복잡 도 (연산 이 간편 하기 위해 서 는 x 가 배열 과 배열 에 없 는 확률 이 각각 0.5 라 고 가정 합 니 다), 평균 계산 복잡 도 는 1 ∗ (1 / 2 n) + 2 ∗ (1 / 2 n) + 2 ∗ (1 / 2 n) +. + n ∗ (1 / 2 n) + n ∗ (1 / 2) = (3 n + 1) / 4 1 / 4 1 * (1 / 2 n) * (1 / 2 n) + 2 * (1 / 2 n) +.... + n * (1 / 2 n) + n * * (1 / 2 n) = (3 n + 1) / 4 1 ? (1 / 2 n) + 2 n) + 2 + 2 + + + + 2 * * (1 / n) + 277 (1 / 2n) +... + n ∗ (1 / 2n) + n ∗ (1 / 2) =(3n+1)/4
계수 와 상 수 를 제거 하고 복잡 도 는 여전히 O (n) 이다.
평균 분담 시간 복잡 도 는 코드 가 실 행 된 모든 복잡 도 상황 에서 대부분 낮은 등급 의 복잡 도 를 말 하 는데 개별 상황 은 높 은 등급 의 복잡 도 이 고 순서 관계 가 발생 할 때 개별 높 은 등급 의 복잡 도 를 낮은 등급 의 복잡 도 에 균등 하 게 분담 할 수 있다.
2. 공간 복잡 도
공간 복잡 도 는 하나의 알고리즘 이 실행 과정 에서 저장 공간 크기 를 임시로 차지 하 는 양 입 니 다. 하나의 알고리즘 이 컴퓨터 메모리 에서 차지 하 는 저장 공간 은 저장 알고리즘 자체 가 차지 하 는 저장 공간, 알고리즘 의 입 출력 데이터 가 차지 하 는 저장 공간 과 알고리즘 이 실행 과정 에서 임시로 사용 하 는 저장 공간 등 세 가지 측면 을 포함 합 니 다. 알고리즘 의 입력 전송데이터 가 차지 하 는 저장 공간 은 해결 해 야 할 문제 에 의 해 결정 되 며, 매개 변수 표를 통 해 호출 함수 에 의 해 전달 되 며, 이 알고리즘 에 따라 달라 지지 않 습 니 다. 흔히 볼 수 있 는 공간 복잡 도 는 O (1), O (n), O (n 2 n ^ 2 n2) 이 며, 공간 복잡 도 분석 은 시간 복잡 도 분석 보다 훨씬 간단 합 니 다.
참고 자료: 왕 쟁 의 데이터 구조 와 알고리즘 의 미