본 내용은 지식공유자 감자님의 강의 기반으로 만들어진 글입니다. (몇개의 이미지는 감자님의 강의 영상에 올라온 내용입니다.)
이전 내용 : 자료구조와 알고리즘
- 같은 자료구조를 쓰더라도 알고리즘은 여러가지가 있다.
- 더 좋은 알고리즘을 사용해야 한다.
- 사용자의 요구에 따라 다르다.
- 메모리를 더 적게 사용하는 것
- 속도가 더 빠른 알고리즘
- 사용자의 요구에 따라 다르다.
시간복잡도
알고리즘속도를 성능의 척도라고 생각한다. : 시간복잡도
- 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
- 그러나 시간을 측정해서 알고리즘을 평가하기엔 어렵다.
- 사용자 마다 컴퓨터 사양이 다르기 때문이다.
그래서 코드에서 성능에 많은 영향을 미치는 것을 수정해야 한다.
이것은 반복문이다.
해당 알고리즘의 반복문을 보고 시간을 판단한다.
- 5를 찾기 위해 간단한 알고리즘 배열의 0번인덱스 부터 5인지 아닌지 확인하는 것이다.
- 첫번째 원소 5가 아니다.
- 두번째 원소 5가아니다
- 세번째 원소 5를 확인했더니 5이다.
길이가 4인 배열에서 3번만에 찾았다.
우리가 찾는 데이터가 배열의 어디에 있는지에 따라 성능은 천차만별이다.
찾는 데이터가 배열의 첫번째 원소에 있다면 한번만에 해결될 것이다.
반면 찾는 데이터가 배열의 마지막 원소에 있다면 최악의 경우 배열의 길이만큼 해서 찾을 수 있다.
중간정도라면 중간정도에 가서 찾을 것이다.
때에 따라 달리진다는 것이다.
경우를 나눠서 나눈다.
최선, 최악, 평균
출처 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) - 감자
주로 Big-O를 사용한다.
최악을 찾는 경우
이 경우 찾는 데이터가 가장 뒤에 있는 경우
만약 입력이 n이라면 배열의 데이터가 n개 있다면 최악의 경우 n번만에 데이터를 찾을 수있다.
일차함수의 모양으로 데이터 수를 나타내는 n에 1을 넣으면 계산량은 1, n에 5를 넣으면 계산량은 5가 된다.
데이터가 많아지면 그에 비례해서 계산량이 많아진다
O(n)은 선형시간 알고리즘이다.
상수시간 알고리즘은 O(1)으로 입력의 크기가 상관없이 상수의 시간이 걸린다는 의미
계산량이 꼭 1번일 필요 없다.
문제를 해결하는데 입력의 크기에 상관없이 100번의 계산이 걸린다해도 상수여서 O(1)으로 표기
성능을 정확히 표현하기 힘들다.
시간복잡도의 종류
보라색으로 갈 수록 성능이 좋지 않은 알고리즘이다.
빅오 표기법의 특징
- 입력이 늘어날때 계산량이 늘어나는 척도 인데.
만약 아래와 같은 성능을 보이는 알고리즘이 있다면 어떻게 표현할까?
- 계산에 가장 많은 영향을 미치는 것 만 표기한다. O(n²)으로 표기한다.
- O(3n²) 으로 표기할 수 있으나.
빅오 표기법 할 때는 상수가 큰 의미가 없으므로 제거해준다.
- O(n²)으로 표기해준다.
'🅴🆃🅲 > 자료구조&알고리즘' 카테고리의 다른 글
| [자료구조와 알고리즘] 자료구조와 알고리즘 이란? (1) | 2024.10.01 |
|---|
