BigO
빅오는 대략적으로 숫자를 세는 것의 붙인 공식적인 표현입니다
정식으로 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인
방식입니다.
다른 내용은 상관 하지 않습니다. 오로지 전반적인 추세에 주못 하는 것입니다.
빅오의 복잡도를 분석할때 매우 복잡해집니다.섬세하게 작은 내용들까지 따질 수도 있겠지만
단순화 한다
왜 빅오 표기법을 사용할까?
결론부터 말하자면 빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다. (알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.)
빅오메가는 하한선을 기준으로하고, 빅세타는 상한선과 하한선의 사이를 기준으로 표기한다.
일상의 대화에서 비유하자면 법정 최고이자율이 24% 인데 친구가 사채대출의 이자율을 물어본다.
(이자율이 높을수록 최악의 경우이다.)
하지만 정확한 법정 최고이자율이 생각나지 않는다.
이때 친구에게 빅오 표기법으로 말하자면 사채대출을 받으면 이자율이 30% 안에서 책정 될거야 라고 말하는 것과 같다.
(실제로 정확하진 않지만 대략 30%를 넘지 않을 것을 알고 모든 경우의 수를 포함하도록 말하는 것이다.)
빅오메가 표기법으로 말하자면 이자율이 0% 이상 일거야 라고 말하는 것과 같다. (사실상 의미가 없다.)
빅세타 표기법으로 말하자면 이자율이 0%(하한) 와 30%(상한) 의 사이쯤 이라고 말하는 것과 같다.
(빅세타는 하한과 상한 사이 평균정도의 의미로 쓰인다.)
여기서 주의할 점은 빅오 표기법이 상한선만 지정했을 뿐 상한선이 꼭 알고리즘 효율성의 최악의 경우는 아니라는 것이다.
예를들어 법정 최고이자율이 24% 라서 사채의 이자율은 24%를 넘을 수 없다. 내가 30% 안이라고 해서 친구가 사채의 이자가 최대 30%까지 될 수도 있겠다고 생각할 필요는 없는 것이다. 이자율이 최악으로 가장 높은 경우인 24% 가 이자율 30% 안에 포함된다는 말일 뿐이다.
- 산수는 상수(Constant) 이다 . 덧셈 뺄셈 곱셈 나눗셈을 포함합니다.
- 변수 배정도 상수(Constant) 이다. 컴퓨터가 변수에 값을 배정하는데 걸리는 시간은 비슷하기때문이다 ex) x=1000를 처리하는것과 x= 2000을 하든 100만을 처리 속도 비슷
- 인덱스를 사용해서 배열 엘리먼트를 접근하는것
- 반복문 (Loop) 있으면 복잡도가 루프의 길이 곱하기 0에서 n까지 간다면, n이 커질 수록 루프가 반복되는 획수가 늘어납니다.
Log
로그함수는 지수함수의 역함이다. 예를 들어 나눗셈과 곱셈이 짝인것처럼 로그함수와 지수함수는 짝이다.
log₂(8)=3 ---------- 2₃= 8
log₂(value) = exponent ---------- 2 exponent = value
