목록코딩테스트 시간복잡도 (1)

코딩뚠뚠

[개념정리] Big - O 시간복잡도 표기

알고리즘 문제를 풀면서 언젠간 한 번쯤 마주할 시간초과를 계산해내기 위한 Big-O 표기법이다. 시간복잡도란 실행시간으로 알고리즘의 효율을 측정한다. 연산 Step 의 수 ex 1부터 N 까지 더할 때 int summ(){ int result = 0; for(int i=1; i O(n^2) T(n) = n^4 + n^3 + n^2 + 1 => O(n^4) T(n) = 5n^3 + 10n^2 => O(n^3) Big-O 표기법의 종류 1 log n n n log n n^2 n^3 2^n O(1) : - 데이터의 양과 상관없이 일정한 실행시간을 가진다 - 상수그래프의 모양을 그린다. O(log n) : - 위와 같은 그래프의 모양을 보인다. - 따라서 데이터양이 많아져도 시간이 조금씩 늘어난다. - bina..
알고리즘 문제풀이/개념정리 2021. 3. 13. 18:22
이전 Prev 1 Next 다음