🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
시간 복잡도
📍 좋은 알고리즘은 무엇일까?
👉🏻 사용자의 요구에 따라 달라짐 (메모리 사용량, 속도 등)
👉🏻 보통은 속도를 좋은 알고리즘의 척도로 사용함
📍 시간 복잡도
👉🏻 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간
👉🏻 단, 사용자마다 컴퓨터 사양이 다르므로 객관적 평가는 불가능
👉🏻 따라서 단순히 걸리는 시간이 아닌 '코드에서 성능에 많은 영향을 주는 부분(반복문의 수)'로 평가
주어진 배열에서 5를 찾으시오.
[1, 3, 5, 7]1) 처음부터 찾는다면?
👉🏻 3번째에 찾게 됨
👉🏻 하지만 이도 5가 어디 있느냐에 따라 달라짐(첫 번째에 찾을 수도 있고, 최악의 경우 배열의 길이만큼 걸림)
📍 표현법
👉🏻 Big-Ω[빅 오메가] 최선의 경우
👉🏻 Big-O[빅오] 최악의 경우: 가장 많이 사용됨
O(n^2)
👉🏻 Big-θ[빅 세타] 평균의 경우
📍 빅오 알고리즘
최악의 경우는 찾는 데이터가 배열의 끝에 있을 때
[1, 3, 7, 5]
👉🏻 일차함수의 모양(/)으로 데이터가 많아지며 그에 비례해서 계산량이 많아짐(선형시간 알고리즘)
👉🏻 입력이 n이라면, 최악의 경우 n번 만에 데이터 찾음
👉🏻 O(n)
📍 상수시간 알고리즘
👉🏻 입력의 크기에 상관없이 상수의 시간이 걸림 O(1)걸림
👉🏻 입력의 크기에 상관없이 100번의 시간이 걸려도 상수이기 때문에 O(1)로 표현
👉🏻 왼쪽으로 갈수록 최악
👉🏻 성능을 말할 때는 이 중 하나로 표현
📍 빅오 표현법 특징
👉🏻 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것
👉🏻 n^2 + 2n + 100을 표현하고자 할 때는 n^2이 가장 많은 영향을 미치므로 O(n^2)로 표시함
👉🏻 3n^2+100은 가장 큰 항을 표시하되, 상수는 큰 의미가 없으므로 3을 버리고 O(n^2)로 표시함