- Reference
- https://blog.chulgil.me/algorithm/
- 재미난 컴퓨터 이야기(y.g)
아래의 설명과 예시는 위 참고자료를 기반으로 하였음을 알립니다.
# 알고리즘
어떠한 목적을 달성하기위한 절차/방법 이다.
헬스 운동을 예를 들어보자. 나는 어깨운동을 통해서 전반적인 어깨의 삼각근 크기를 늘리는 목적으로 헬스장에서 운동을 하는 것이다. 이때 효율적으로 운동을하여 짧은시간안에 효율적인 운동효과를 보고싶다. 그래서 어깨의 전면, 상부, 후면, 그리고 어깨 전체를 사용하는 4가지를 운동을 15회 5Set씩 각각 진행해보려 한다.
func workOutShoulder() {
- 나에게 맞는 아령을 고른다. 3kg
- 아령을 들고 전면을 15회를 한다.
- 30초 휴식을한다.
- 5Set까지 15회 후 30초 휴식을 4번 더 반복한다.
- 1분 휴식을한다.
- 측면을 15회 1Set 한다.
- 30초 휴식을한다.
- 5Set까지 15회 후 30초 휴식을 4번 더 반복한다.
- 1분 휴식을한다.
- 후면을 15회 1Set 한다.
- 30초 휴식을한다.
- 5Set까지 15회 후 30초 휴식을 4번 더 반복한다.
.
.
.
}알고리즘이란 어떠한 목적을 달성하기위한 절차/방법이다.
그런데 어깨운동을 하는 알고리즘은 사람과 상황에따라 다르다. 그래서 더 효율적인 방법을 판단하기위해 시간 단축을 하는 방법에는 사람마다 다를 수 있다. 따라서 시간복잡도가 낮은 알고리즘을 선택하는 것이다.
기본적으로 컴퓨터의 성능, 사용하는 언어, 컴파일러의 속도에따라 시간복잡도가 계산된다고 한다.
이를 계산하고 표기하는 방법에는
크게 3가지가 존재한다.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
평균인 세타 표기를 하면 정확하게 계산할 수 있지만 평가하기가 까다롭다고 한다.
그래서 최악의 경우인 빅오를 사용하여 알고리즘이 최악일때의 경우를 판단한다.
왜냐하면 평균과 가까운 성능으로 예측하기 쉬운 방법이기 때문이다.
# 시간복잡도
- 알고리즘이 실행되는데 소요하는 시간을 분석한것, 알고리즘의 성능을 나타내는 기준이다.
유사한 말로는 알고리즘의 연산을 수치화한것이라고도 하는데 수치화를 하는 이유는 컴퓨터의 성능, 사용하는 언어에따라서 정확도가 다르기때문에 명령어의 실행 횟수만을 고려하는 것이다.
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
O(1) : 상수
func workOut() {
print("어깨운동을 시작합니다.")
}
O(N) : 선형
입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.
func workOut(set: Int) {
for _ in 1..<set {
print("어깨운동")
}
}
O(N^2) : Square
이중 포문
func workOut(set: Int) {
for _ in 1..<set {
for _ in 1..<set {
print("어깨운동")
}
}
}
O(log n) O(n log n)
이는 입력 크기의 따라 처리시간이 증가하는 알고리즘에서 많이 사용된다고한다. 이 예시는 참조 링크를 참고하자
시간복잡도를 구하는 요령에대해서 위의 참조자료를 참고했다.
# [시간복잡도를 구하는 요령]
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
자료구조 비교
정렬 알고리즘 비교
'알고리즘' 카테고리의 다른 글
| 알고리즘 공부 참고자료 (0) | 2022.02.09 |
|---|