자료구조[알고리즘 시간복잡도]/알고리즘 복잡도 계산이 필요한 이유

하나의 문제를 푸는 알고리즘은 다양할 수 있다.

 

 

정수의 절대값 구하기

 

1, -1 -->> 1

 

방법1: 정수값을 제곱한 값에 다시 루트를 씌우기

방법2: 정수가 음수인지 확인 해서, 음수일 때만 -1을 곱하기

 

알고리즘 시간 복잡도의 주요 요소

반복문이 지배한다.

생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?

예:

자동차로 서울에서 부산가기

1. 자동차 문열기
2. 자동차 문닫기
3. 자동차 운전석 등받이 조정하기
4. 자동차 시동걸기
5. 자동차로 서울에서 부산가기
6. 자동차 시동끄기
7. 자동차 문열기
8. 자동차 문닫기

다른 것은 시간이 얼마 안 걸리나, 5번은 시간 소요에 가장 많이 미친다.

마찬가지로 프로그래밍 알고리즘에서도 시간복잡도에서 if문을 몇개 썼을 때, 변수를 몇개 선언 그런 것이 문제가 아니라, 반복문을 어떻게 구성했는지에 따라 알고리즘의 성능,시간이 달라질 수 있다.

반복문으로 만든 알고리즘 안 반복의 횟수가 굉장히 차이가 나기 때문에 시간복잡도가 차이가 많이 난다.

알고리즘 성능 표기법

Big O(빅-오)표기법: O(N)

• 알고리즘 최악의 실행 시간을 표기
• 가장 많이/일반적으로 사용한다.
• 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이다.

오메가 표기법

최상의 실행 시간을 표기

세타 표기법

평균 실행 시간을 표기

대문자 O 표기법

빅 오 표기법, Big-O 표기법 이라고도 부른다.

O(입력)

• 입력 n 에 따라 결정되는 시간 복잡도 함수
• O(1), O(logn), O(nlogn), O(n2),O(2n),(O(n!)등으로 표기한다.
• 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다.
• O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)

실제 실행시간은 다 다를 수가 있다.

그런데 다른 알고리즘과 비교를 하면, 어떤 알고리즘은 O(n), 내가 알고리즘은 O(1)

이라고 했을 때, O(n)보다 성능이 좋다라고 할 수 있다.

단순하게 입력 "n"에 따라, 몇번 실행 되는지를 계산하면 된다.

표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다.

n이 1이든 100이든, 1000이든, 10000이든 실행을

무조건 2회(상수회) 실행한다: O(1)

예) n이 100인데,

코드는 if를 쓴다고 가정하자.

if n > 10:

   print(n)

이런 코드라고 했을 때, 만약에 n에 1,100,1000 숫자던 간에 코드 두 줄만 실행하면 끝이다.

n에 따라서 변경되는 것이 없다.

n에 따라, n번, n + 10 번, 또는 3n + 10 번등을 실행한다 : O(n)

for index in range(n):

print(index)

n이 1번이면 반복문이 1번 밖에 안된다.

근데 n이 10번이면 10번 실행한다.

n이 10000번이면 10000번 실행한다. 이럴 때는 O(n)이라고 표기한다.

n에 따라, n²번, n² + 1000 번, 100n² - 100번,또는 300n² + 1번등 실행한다: O(n²)

variable = 1

for i in range(300):

	for num in range(n):

 		for index in range(n):

                      	print(index)

빅오 입력값 표기 방법

예 :

만약 시간 복잡도 함수가 2n² + 3n 이라면

1.가장 높은 차수는 2n²

2.상수는 실제 큰 영향이 없다.

3.결국 빅 오 표기법으로는 O(n²)

연습1: 1부터 n까지의 합을 구하는 알고리즘 작성해보기

//방법 1
def sum_all(n):
	total = 0
	for num in range(1, n + 1):
  		total += num
return total
sum_all(100)

//방법 2
n(n+1)
------
   2   
  
def sum_all(n):
  return int(n * (n + 1)/2)

sum_all(100)

5050

방법 1을 시간복잡도로 생각해보면, 반복문은 실제로 n번 돌기에 시간복잡도는 n이 된다.

시간 복잡도는 n이고 빅오 표기법으로는 O(n)이다.

이에 반해, 방법2는 1이고, 빅 오 표기법은 O(1)이다.

방법1과 방법2 중에 어떤 것이 더 좋냐면,

O(1)이 성능이 더 좋다고 볼 수 있다.

 

 

참고: https://fastcampus.co.kr/courses/210773/clips/