반응형 빅오3 점화식 Recusion Tree로 풀기 [ 점화식 기본 수식 ] 재귀의 기초 지식 내용을 알아보기 전에 아래의 수식이 어떤 시간 복잡도를 가지고 있는지를 눈으로 읽혀둔다. 처음 봤을 때는 이게 무슨 말인지 모를 수도 있지만, 나중에 딱 이 수식만을 알기 위해 찾을 경우가 존재하므로 글의 가장 상단에 위치시켰다. 하나의 항목을 제거하기 위해 입력을 반복하는 재귀 알고리즘이다. $$T(n) = T(n-1) + n => O(n^2)$$ 입력을 2개로 분할 후, 정렬 작업을 수행하는 재귀 알고리즘이다.(Quick Sort, Merge Sort) $$T(n) = 2T(n/2) + cn => O(nlogn)$$ 하나의 단계마다 입력을 절반으로 줄이는 재귀 알고리즘이다.(Binary Search) $$T(n) = T(n/2) + c => O(logn)$$.. 2021. 4. 21. 빅오(Big O) 시간복잡도 [ Big O, 시간복잡도 ] 빅오(Big O) 시간복잡도는 위 그림하나도 전부 설명이 가능하다. 빅오는 처리시간이 아니라 시간의 증가율을 나타낸다고 보면 된다. X는 데이터의 갯수, Y는 처리의 갯수이다. 순서를 보면 $O(2^n)$ > $O(n^2)$ > $O(n log n)$ > $O(N)$ > $O(log n)$ > $O(1)$ 이다. 참고로 빅오 표기법에서 상수는 연산에 고정된 값이라서 연산에 크게 작용하지 않는다고 본다. 그래서 상수 10을 빅오랑 곱해도 값은 빅오 그대로 라는 것을 알아야 한다. 예를들어 $10 \times O(1)$ = $O(1)$ 이다. 시간 증가량에 대한 표기법은 점근적 상한(Upper Bound)인 Big-O 외에 점근적 일치(Tight Bound)인 Big-Theta.. 2021. 4. 10. 인터뷰에서 중요한 알고리즘 질문 1 [ 알고리즘 기초 ] #알고리즘 이란? 어떤 문제나 과제를 해결하기 위한 단계적 방법이다. 알고리즘에는 3가지 요소가 있는데 그것은 Sequence, Decision, Repetition 이다. 3가지를 풀이하면, 1) 순서가 있어야 하고 2) 조건에 따른 실행이 가능하고 3) 반복적으로 실행이 가능한 것을 말한다. 1) ~ 3)까지 유한 시간 내 반드시 종료가 돼야 하고 수행의 결과가 존재해야 한다. 부 알고리즘(subAlgorithms)은 복잡한 알고리즘 안에 있는 부분 알고리즘이다. 주 알고리즘과 부 알고리즘의 관계는 Structure Chart로 확인이 가능하다. 이런 용어를 하나씩 인지하고 있으면 언제나 도움이 된다. 알고리즘을 표현하는 방법으로는 UML과 Pseudocode가 있다. UML은 .. 2020. 4. 27. 이전 1 다음 반응형
