1. 시간 복잡도 / 공간 복잡도 판단하기 + 접근 표기법
- 시간복잡도란?
-> 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이다. 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.
- How to define Time Complexity?
-> 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하면 된다.
ex)
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return max_num-> 위 코드의 시간복잡도는 array의 길이 X array의 길이 X 비교 연산 1번으로 N x N 즉, N^2 n제곱의 시간복잡도를 가진다.
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행-> 위 코드의 시간복잡도는 max_num 대입 연산 1번, array의 길이 X (비교 연산 1번 + 대입 연산 1번)으로 총 1 + 2 x N, 즉 2N + 1 만큼의 시간복잡도를 가진다고 볼 수 있다.
- 각각의 비교 / 대입 연산을 모두 계산해서 판단하는 것은 코드가 복잡해지고 길어질 수록 판단하기도 힘들고, 데이터로 비교했을 때 n^2, N의 제곱으로 N의 값의 크기에 따라 크게 변동사항이 있는 n에만 집중해서 계산하면 되기 때문에, 다른 상수 시간의 연산은 따로 계산하지 않아도 된다.
- 공간복잡도란?
-> 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 뜻한다. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것인데, 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.
- How to define Space Complexity?
-> 저장하는 데이터의 양이 1개의 공간을 사용한다고 생각하고 계산하면 된다.
- 시간복잡도 vs 공간복잡도. 어느것에 더욱 집중해서 코딩해야할까?
-> 예제를 통해서 52N + 104 든 3N+106 이든 N^2 에 비해서 아무것도 아니다. 즉, 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다는 것을 알 수 있었다.
- 접근표기법이란?
-> 알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 “효율성”을 평가하는 방법으로, 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.
-> 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다.
- 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지,
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기한다.
ex)
같은 코드를 두고, 최악의 경우의 수인 빅오 표기법으로 표시하면 O(N), 최선의 경우의 수인 빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다라고 각각 표기할 수 있다.
