안녕하세요~ jchoi에요 오늘은 시간 복잡도와 점근 표기법에 대해 이야기해 볼게요! 알고리즘 분석에서는 주로 시간 복잡도에 관심을 두고, 이 알고리즘이 얼마나 좋은 성능을 내는지 (얼마나 빨리 답을 낼 수 있는지)를 생각합니다!
일반적으로 n (입력자료의 크기)에 비례해서 알고리즘은 연산시간이 증가(느려짐)하게 됩니다. (입력 자료가 늘어날수록 빨라지는 알고리즘도 있나요..?? 제가 몰라서 혹시 있으면 댓글로 적어주세요!)
알고리즘 책에서 흔히 나오는 수학적 정의와 도표를 보자면!
보통 이런 기호 나오면 바로 내려버리신단 말이에요 그래서 제가 쉽게 써봤습니다
이렇게 할거였으면 팔만코딩경 안쓰고 그냥 링크 복붙하는게 낫죠!
무한끼리 비교하는 방법을 알아봅시다. 우선 점근표기법은, 시간 복잡도 함수로 표현된 f(n)에서 n을 무한으로 보내 비교하는건데 알아두셔야 할 점은 무한에도 급이 있다는 겁니다. 말하자면 무한끼리 대결을 시켜서 서열을 나누는 거죠
그럼 어떻게 비교를 하는가? A : “난 무한이야” B : “웃기시네! 난 더 무한이야!” C: “난 더더무한이거든!” (.. 이렇게 할리는 없겠져? ㅎㅎ.. 죄송합니다)
무한끼리의 이런 힘싸움?은 서로 나눈 식을 n을 무한으로 보냈을 때의 결과로 결정되는데요 그림을 봅시다!
이런 ‘양으로 발산하는 함수의’ 극한들의 힘싸움의 결과는 다음의 3가지입니다.