Fact
- 3일차!!
Feeling
- 오늘도 힘든 하루였다.
Finding
빅오 표기법
문제 크기 n(일반적으로 항목 수입니다.)이 주어 졌을때 알고리즘을 실행 할때 필요한 시간이나 메모리의 측도이다. 방정식 f(n) = O(g(n)는 방정식의 크기가 g(n)의 일정 배수보다 작다는 것을 의미한다. 표기법에는 “n의 f는 n의 g의 big O”이라고 쓰여 있다.
- 빅 오 표기법은 알고리즘이 얼마나 복잡한지를 기술하기 위해 컴퓨터 공학에서 사용되는 수학 함수로서, 보다 구체적으로 알고리즘에 의해 요구되는 실행 시간을 기술한다. 소프트웨어 공학에서는 다른 접근방식의 효율을 문제와 비교하기 위해 사용된다.
- Big O Notation은 입력이 임의로 커짐에 따라 입력에 비해 얼마나 빨리 증가하는지 측면에서 런타임을 표현한다. 본질적으로, 그것은 알고리즘이 얼마나 확장 가능한지에 대한 통찰력을 끌어내는 방법이다. 알고리즘이 얼마나 빨리 작동 하는지 또는 얼마나 느리게 작동 하는지 알려주지 않고 대신 알고리즘이 입력 크기에 따라 어떻게 변하는지 알려준다.
- 여기서 복잡도가 두개로 나눠 진다. 시간복잡도와 공간 복잡도.
- 최고의 케이스일땐 빅 오메가Ω(n)
- 평균 케이스 일땐 빅 세타Θ(n)
- 최악의 케이스 일땐 빅오 O(n)
bigO 종류
-
O(1) - 일정 시간 복잡도 이것은 고정 런타임으로 해석된다. 즉, 입력의 크기와 상관없이 알고리즘은 동일한 런타임을 가질 것이다.
- 예) 배열 삽입/가져오기 Array: inserting or retrieving an element
- O(log n) - 로그 시간 복잡성 O(log n)는 시간이 선형적으로 증가하는 반면 n은 기하급수적으로 증가하는 것을 의미한다. 그래서 10개 원소를 계산하는 데 1초가 걸린다면 100개 원소 등을 계산하는 데 2초가 걸린다. 우리가 분할 및 정복 알고리즘을 사용할 때(예: 바이너리 검색) O(log n)이다
-
O(n) - 선형 시간 복잡성 O(n)는 입력 데이터 세트의 크기에 비례하여 선형적으로 성능이 증가하는 알고리즘을 설명한다.
- Tree: DFS tree
-
O(n²) - 2차 시간 복잡성 목록의 요소가 증가함에 따라 알고리즘을 실행하는 데 걸리는 시간은 기하급수적으로 증가할 것이다.
- 정렬 알고리즘: 버블 정렬 및 삽입 정렬
출처: Big O Notation: A primer for beginning devs
Future Action
- 불필요 한것을 짜다 시간을 많이 허비 했다. 다음에는 요구 사항을 만족 시킨 다음에 추가 하는걸로 해보자.