목록전체 글 (158)
Nagie's DevStory
O(log n)은 이진 로그(logarithmic) 시간 복잡도를 가지는 알고리즘을 나타낸다. 이는 입력 크기 n에 대해 로그의 형태로 실행 시간이 증가하는 알고리즘을 의미한다. 주로 이진 탐색과 같은 분할 정복 알고리즘에서 발생하며, 큰 데이터셋에서 효과적으로 동작하는 특성 덕에 탐색이나 정렬과 같은 문제에서 자주 사용된다. int binarySearch(int arr[], int left, int right, int target) { while (left
O(2ⁿ)은 입력 크기 n에 대해 2의 n 제곱에 비례하는 지수 시간 복잡도를 갖는 알고리즘을 나타낸다. 이는 입력 크기가 증가함에 따라 실행 시간이 기하급수적으로 증가하는 경우이며, 주로 재귀 알고리즘에서 이러한 시간 복잡도가 발생한다. 아래는 O(2ⁿ)의 시간 복잡도를 가지는 피보나치수열을 구하는 코드이다. int fibonacci(int n) { if (n
O(n²)은 입력 크기 n에 대해 제곱 비례하는 시간 복잡도를 가지는 알고리즘을 나타낸다. 즉, 입력 크기가 증가함에 따라 실행 시간이 제곱으로 증가하며 이는 일반적으로 중첩된 반복문이 있는 경우 발생한다. O(n²)의 시간 복잡도를 갖는 알고리즘의 예시로는 다음과 같은 이중 반복문이 있다. void bubble_sort(int data[], int n) { for (int i = (n - 1); i > 0; i--) { //이중 for 반복문 내부 문장이 ½n(n - 1)번 실행 : O(n) for (int j = 0; j data[j + 1]) { swap(data[j], data[j + 1]); } } } }
O(n)은 선형 시간 복잡도를 나타내며, 입력 크기에 선형으로 비례하여 실행 시간이 증가하는 알고리즘을 의미한다. 즉, 입력 크기가 n일 때, 실행 시간은 n에 정비례한다. 예시 1 int summation(int data[], int n) { int sum = 0; for (int i = 0; i < n; i++) { //for 반복문 내부 문장이 n번 실행 : O(n) sum = sum + data[i]; } return sum; } 예시 2 int variance(int data[], int n) { int sum = 0; for (int i = 0; i < n; i++) { //for 반복문 1 sum = sum + data[i]; } double mean = static_cast(sum) / n..