빅오 표기법
알고리즘을 구현하는 법을 학습하기 전에 알고리즘이 얼마나 효과적인지 분석하는 법을 이해해야 한다.
빅오 표기법이란?
빅오(Big-O) 표기법은 시간 및 알고리즘 공간 복잡도를 분석하기 위한 개념인데, 알고리즘의 최악의 경우 복잡도를 측정하여 효율성을 표기한다고 생각하면 된다.
빅오(Big-O) 표기법에서 n은 입력의 개수를 나타내는데, 빅오와 관련된 질문으로 "n이 무한으로 접근할 때 어떻게 될까?"가 있다.
빅오 표기법은 알고리즘을 구현할 때 해당 알고리즘이 얼마나 효율적인지 나타내기 때문에 중요하다고 볼 수 있다
빅오 표기법 규칙
알고리즘의 시간 복잡도를 f(n)이라고 표현하면 n은 입력의 개수 , f(n)time 은 필요한 시간 , f(n)space 는 필요한 공간(추가적인 메모리)을 나타낸다.
알고리즘 분석의 목표는 f(n) 을 계산함으로써 알고리즘의 효율성을 이해하는것이다.
하지만 f(n)을 계산한다는 것은 굉장히 어려울 수 있는데, 이를 위해 개발자 형님들이 f(n)를 계산하는데 도움이 되는 기본적인 규칙을 제공한다.
- 계수 법칙: 상수 k가 0보다 크다고 할 때 ( k>0), f(n) 이 O(g(n))이면 kf(n)은 O(g(n))이다.
f(n) 이 O(n^2) 이면 kf(n) 도 O(n^2) 라는 뜻인듯
- 합의 법칙: f(n) 이 O(h(n)) 이고 g(n)이 O(p(n)) 이면 f(n) + g(n) 은 O(h(n)+p(n)) 이다.
즉 두 개의 알고리즘이 있고 각각의 시간복잡도 가 있을 때 빅오 표기법 더할수 있다는 뜻.
-
곱의 법칙: (n) 이 O(h(n)) 이고 g(n)이 O(p(n)) 이면 f(n) g(n)은 O(h(n)p(n))
마찬가지로 두 개의 알고리즘이 있고 각각의 시간복잡도 가 있을 때 빅오 표기법 역시 곱해진다. -
전이 법칙: f(n)이 O(g(n)) 이고 g(n)이 O(h(n)) 이면 f(n)은 O(h(n)) 이다.
눈물이 날거같음 -
다항 법칙: f(n)이 k차 다항식이면 f(n)은 O(n^k) 이다.
계수, 합, 곱, 다항 법칙이 일반적으로 많이 쓰인다고 한다.
자세한건 다음 시간에..
Author And Source
이 문제에 관하여(빅오 표기법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ldu_95/빅오-표기법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)