알고리즘 핵심 - 공간 복잡 도와 시간 복잡 도 초 상세 분석

알고리즘 핵심 - 공간 복잡 도와 시간 복잡 도 초 상세 분석
알고리즘
알고리즘:

유한 명령 집합

일부 입력 을 받는다 (어떤 경우 에는 수입 이 필요 없다)

출력 발생

유한 절차 후에 반드시 종료

모든 명령 은 반드시:

명확 한 목표 가 있 고 나 쁜 뜻 이 있어 서 는 안 된다

컴퓨터 가 처리 할 수 있 는 범위 내

설명 은 그 어떠한 컴퓨터 언어 와 구체 적 인 실현 수단 에 의존 하지 않 아야 한다

.
사실은 말하자면 알고리즘 은 계산 과정 에서 문 제 를 해결 하 는 방법 이다.우 리 는 데이터 구조 가 데 이 터 를 어떻게 저장 하 는 지 이미 알 고 있다. 그러나 '프로그램 = 데이터 구조 + 알고리즘' 은 데이터 구조 가 정적 이 고 알고리즘 은 동적 이 며 그것들 을 합치 면 프로그램 이다.
알고리즘 에 있어 서 입력 이 있 고 출력 이 있 으 며 함수 에 매개 변수 가 반환 값 이 있 는 것 과 같 습 니 다.우 리 는 알고리즘 을 쓸 때 습관 적 으로 알고리즘 을 함수 에 봉 한다.
2. 무엇이 좋 은 알고리즘 입 니까?
자, 위 에서 우 리 는 알고리즘 이 무엇 인지 알 게 되 었 습 니 다. 다음은 제 가 좋 은 알고리즘 이 무엇 인지 말씀 드 리 겠 습 니 다.같은 문 제 를 해결 할 때 우 리 는 보통 여러 가지 다른 알고리즘 이 있 습 니 다. 차이 점 은 어떤 알고리즘 이 비교적 멍청 하고 어떤 알고리즘 이 비교적 똑똑 하 다 는 것 입 니 다. 그러면 우 리 는 그들 이 누가 좋 고 누가 나 쁜 지 어떻게 평가 합 니까?우 리 는 보통 다음 과 같은 두 가지 지표 가 있다.

공간 복잡 도: 알고리즘 에 따라 작 성 된 프로그램 이 실 행 될 때 저장 장치 의 길 이 를 차지한다.

시간 복잡 도: 알고리즘 에 따라 작 성 된 프로그램 이 실행 할 때 시간 을 소모 하 는 길이 입 니 다.

먼저 예 를 들 어 10 개의 정 수 를 인쇄 하 라 고 하면 그 프로그램 은 순식간에 결 과 를 낼 수 있 습 니 다. 10 만 개의 정 수 를 인쇄 하 라 고 하면 요?좀 더 기 다 려 야 겠 다.그래서 이 프로그램 이 실행 되 는 시간 은 당신 이 처리 해 야 할 데이터 가 10 개 인지 10 만 개 인지 와 관련 이 있 습 니 다. 이 10 또는 10 만 개 는 우리 가 처리 해 야 할 데이터 의 규모 입 니 다.우 리 는 그것 을 n 이 라 고 부 릅 니 다. 변수 라면 이 프로그램 이 사용 하 는 시간 과 공간 은 모두 이 n 과 직접적인 관계 가 있 습 니 다.한 문 제 를 해결 하 는 데 는 여러 가지 방법 이 있 는데, 너 는 이 방법 을 설계 할 때 반드시 이 두 가지 요 소 를 분명하게 고려 해 야 한다.조심 하지 않 으 면 공간 복잡 도가 너무 크 면 그 프로그램 이 바로 터 질 수 있 습 니 다. 비정 상 중단 입 니 다. 제 가 나중에 말씀 드 리 겠 습 니 다. 시간 복잡 도가 너무 크 면 오래 기다 리 지 못 할 수도 있 습 니 다.
시간 복잡 도
먼저 위의 그림 속 의 몇 개의 코드 를 보 세 요. 저 는 Python 으로 표 시 했 습 니 다. 볼 때 두 가지 문 제 를 고려 하 세 요.
 

네 개의 코드 중 어느 그룹의 운행 시간 이 가장 짧 습 니까?

알고리즘 운행 의 속 도 를 어떤 방식 으로 나 타 냅 니까?

방금 말 했 듯 이 n 은 데이터 의 규모 로 볼 수 있 고 규모 가 다 르 며 운행 시간 도 다 를 것 이다. 또한 사용 하 는 시간 도 확실 하지 않 고 서로 다른 n 은 서로 다른 시간 을 얻 을 수 있 기 때문에 우 리 는 시간 복잡 도 를 이용 하여 알고리즘 운행 의 속 도 를 나타 낸다.먼저 아래 그림 속 의 몇 가지 생활 속 의 사건 을 살 펴 보고 시간 을 추정 합 니 다.
여기 서 우 리 는 '몇' 으로 대략적인 것 을 표시 하고 그 뒤에 해당 하 는 시간 단위 가 있다 는 것 을 알 게 될 것 이다. 그 시간 복잡 도 는 비슷 한 방법 을 참조 할 것 이다. 시간 복잡 도: 알고리즘 운행 효율 을 평가 하 는 한 식 으로 위의 그림 을 보면 print ('Hello World') 라 고 할 수 있다. 그의 시간 복잡 도 는 O (1) 이 고 O 는 엄 밀 히 말 하면 수학 상의 상 계 를 나타 낸다.우 리 는 간단하게 위 에서 말 한 '몇' 에 해당 하 는 추정 으로 이해 할 수 있다.1. 실행 단위 (초 와 같은 단위) 로 이해 할 수 있 습 니 다. 왜 O (1) 인지 알 수 있 습 니 다. print ('Hello World') 는 한 번 만 실 행 했 기 때 문 입 니 다. 같은 이치 로 두 번 째 를 분석 합 니 다.
 

for i in range(n):
    print('Hello World')

이 코드 가 n 회 실 행 했 기 때문에 시간 복잡 도 는 O (n) 로 표 시 됩 니 다.n. 역시 단위, 동 리, 세 번 째 분석:

for i in range(n):
    for j in range(n):
        print('Hello World')

그것 의 시간 복잡 도 는 O () 를 나타 내 는데 2 층 순환 이 있 기 때문에 예, 단위 입 니 다.네 번 째 는 네가 스스로 분석 할 수 있 으 니 나 는 쓸데없는 짓 을 하지 않 겠 다.하지만 이렇게 간단 하 다 고 생각 하지 마 세 요. 다음 코드 사진 을 다시 보 겠 습 니 다.
이 그림 을 보면 기분 이 좋 지 않 습 니까? 당신 이 맞 히 는 것 과 차이 가 많 지 않 습 니 다. 하하, 너무 일찍 기뻐 하지 마 세 요. 틀 렸 습 니 다. 그들의 시간 복잡 도 는 이 렇 지 않 습 니 다.왜?내 가 '1' 은 단위 라 고 했 지만 '3' 은 단위 가 아니 라 3 은 3 곱 하기 1 이다. 예 를 들 어 생활 속 에서 물 한 주전 자 를 얼마나 끓 이 느 냐 고 물 었 더 니 아무 도 3 분 이나 3 분 이 라 고 대답 하지 않 았 다.그리고 두 번 째 는 직장 이 고 n 도 직장 이지 만 n 보다 큽 니 다. 그래서 우 리 는 예상 할 때 큰 직장 을 사용 하 는 것 이 마치 생활 속 에서 당신 에 게 얼마나 잤 는 지 물 어 보 는 것 과 같 습 니 다. 당신 은 보통 몇 시간 이 라 고 말 하 는 것 이지 몇 시간 몇 분 이 라 고 말 하 는 것 이 아 닙 니 다. 당신 이 강조 하 는 것 은 대략적인 시간 입 니 다. 아 시 겠 죠?그래서 정확 한 시간 복잡 도 는 이렇다.
첫 번 째 는 왜 O (1) 입 니까? 먼저 print ('Hello World') 를 한 번 인쇄 하고 세 번 인쇄 하 는 것 은 실제 적 인 영향 이 크 지 않 습 니 다. 몇 번 을 실행 하 든 n 만큼 규모 가 크 지 않 을 때 다시 말 하면 1 은 단위 이기 때문에 어쨌든 비슷 하 다 는 뜻 이 고 정확 하 다 는 뜻 이 아니 기 때문에 O (1) 입 니 다. 좋 습 니 다.다음 그림 을 보 세 요. 순환 이 반 으로 줄 어 들 면 시간 복잡 도가 O (logn) 로 변 합 니 다.따라서 알고리즘 과정 이 반복 적 으로 반 으로 접 힐 때 복잡 도 식 에 logn 이 나타 날 수 있다 는 것 을 이렇게 기억 할 수 있 습 니 다.
 
시간 복잡 도 소결

시간 복잡 도 는 알고리즘 운행 시간 을 계산 하 는 데 사용 되 는 식 (단위)

이다.

일반적으로 시간 복잡 도가 높 은 알고리즘 은 시간 복잡 도가 낮은 알고리즘 보다 느리다

흔히 볼 수 있 는 시간 복잡 도 (효율 에 따라 정렬)
복잡 한 문제 의 시간 복잡 도
어떻게 간단 하고 신속하게 알고리즘 의 복잡 도 를 판단 합 니까
공간 복잡 도
공간 복잡 도 에서 주의해 야 할 점 은 바로 '공간 교환 시간' 을 이해 하 는 것 이다. 하나의 알고리즘 을 연구 할 때 시간 이 공간 보다 중요 하 다.
 
이 편 은 끝나다