시간 복잡도

✅본 강의는 쉬운코드의 시간복잡도 강의 영상을 정리한 글입니다!

강의 보러가기

 

---

실행 시간이란?

: 함수/알고리즘 수행에 필요한 스텝(step) 수

( 각 라인을 수행하기 위해 필요한 step수는 상수라고 가정 )

각 라인의 cost * time한 값들을 더한다.

 

💡 T(N) = c1 + c2*(N+1) + c3*N + 1              = (c2 + c3)*N + c1 + c2 + 1              = a*N + b

* N = size of inputs

 

여기서 N이 무한으로 갈 때의 시간이 궁금하다.

 

N이 커질수록 덜 중요한 것은 제거하자.

따라서, 최고차항만 의미가 있다.

( 최고차항의 계수[a]와 b는 의미가 없음)

a*N + b = O(N)

 

이를 점근적 분석이라고 한다.

: 임의의 함수가 N→∞ 일 때 어떤 함수 형태에 근접해지는지 분석

한마디로

시간 복잡도는 함수의 실행 시간을 점근적 분석을 통해 점근적 표기법으로 단순하게 표현

 

---

Case별 점근적 분석

 

 

위 함수의 파라미터 데이터에 따라 실행 시간이 조금씩 달라짐

배열에 초반에 있을 수록 실행시간 줄어듬

이럴 땐, best 케이스와 worst 케이스를 구한다

 

 

 

lower bound(하한선) : 함수 실행 시간은 아무리 빨라도 상수 시간 이상

= Ω(1) = 상수 시간으로 처리

upper bound(상한선) : 함수 실행 시간은 아무리 오래 결려도 N에 비례하는 정도 이하

= O(n)

 

best 케이스와 worst 케이스의 각 하한선과 상한선을 표기해보자

 

하한선과 상한선의 숫자가 같을 때, 비로소 시간 복잡도를 사용할 수 있다.

이 경우를 tight bound라고 함

 

avg case는 절반 정도 왔을 때 찾으려는 target이 있다고 가정하고 구한다.

N/2 = N (/2는 의미 없음)

따라서 θ(N)

---

 

이진탐색에서의 시간 복잡도

worst : 찾는게 없을 경우

target과 비교하는 과정에서 배열이 1/2가 되므로

input size를 N이라고 할 때

N∗(1/2)k=1N*(1/2)^k=1N∗(1/2)k=1

N=2kN=2^kN=2k

k=log(2:밑)Nk = log(2:밑)Nk=log(2:밑)N세

세타(logN)

best : 한번에 찾았을 때

세타(1)

case별 시가 복잡도

예제1

void prints(int[] inputs) {     for(int i=0;i<inputs.length;i++) {         for(int j=0;j<inputs.length;j++) {             System.out.println("최고십니다.");         }     } }

아무리 오래 걸려도 N*N에 비례한 정도를 벗어나지 않는다

아무리 빨리 실행해도 N*N에 비례하는 정도는 걸린다.

정답 : 쎄타(N^2)

예제2

void prints(int[] inputsA, int[] inputsB) {     for(int i=0;i<inputsA.length;i++) {         System.out.println("여러분");     }     for(int j=0;j<inputsB.length;j++) {         System.out.println("알라뷰");     } }

아무리 오래 걸려도 N+M에 비례한 정도를 벗어나지 않는다

아무리 빨리 실행해도 N+M에 비례하는 정도는 걸린다.

N과 M중 더 큰 값의 의해 시간이 결정된다 (다른 하나는 작아서 의미가 없음)

정답: 쎄타(N+M) = 쎄타(max(N,M))

에제3

void prints(int[] inputsA, int[] inputsB) {     for(int i=0;i<inputsA.length;i++) {         for(int j=0;j<inputsB.length;j++) {             System.out.println("최오 표기

대표 시간 복잡도의 속도 비교

O(1)<O(logN)<O(N)<O(N∗logN)<O(N2)<O(2N)<O(N!)O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)O(1)<O(logN)<O(N)<O(N∗logN)<O(N2)<O(2N)<O(N!)비

빅오 표기법을 많이 쓰는 이유

1. 일반적으로 upper bound만 알아도 충분
2. 다른 bound를 계산하기 귀찮아서
3. 괜히 tight bound로 말했다가 태클 받기 싫어서
4. 주위에서 다들 그래서
5. 실은 점근적 표기법의 개념을 잘 몰라서

Uploaded by Notion2Tistory v1.1.0