빅오표기법의 문제풀이
아래 코드들의 시간복잡도를 구한다.
결국 a가 될때까지 b를 몇번 더할 것인지 묻는 문제이다. 아래와 같은 식이 성립한다.
b*n = a
n = a/b
따라서 시간복잡도는 O(a/b) 이 된다.
g가 루트 n이 될 때까지 반복문을 수행하고 있다.
따라서 시간복잡도는 O(sqrt(n)) 가 된다.
만약 이진탐색트리가 균형이 맞지 않는다면, 최악의 경우, 얼마만큼의 시간복잡도를 갖게 되는가?
이진탐색트리의 경우, 최대 2개의 자식을 가진 노드가 층을 이루는 구조이다. 그런데 이때, 각 노드가 각각 하나의 자식을 가진채로 길게 한쪽으로만 늘어서 있다면, 결국 시간복잡도는 노드의 개수만큼 늘어나게 된다.
따라서 시간복잡도는 O(n) 이 된다.
이진탐색트리가 아닐 경우, 트리 내의 특정 요소를 찾는데 걸리는 시간은 얼마일까?
이진탐색트리가 아닌 경우, 최악의 경우, 특정 요소를 찾기 위해서는 모든 노드를 스캔해야할 수 있다.
따라서 시간복잡도는 O(n)이 된다.
배열을 복사하는 함수가 있다. 복사할 배열이 매개변수로 전달되면, 길이가 0인 배열을 초기화하고, 복사할 배열을 순회하며 매번 기준 배열에 길이를 1씩 증가한 배열을 새롭게 정의하여 요소를 추가해준다. 이 경우, 시간복잡도는 얼마이겠는가
array 길이만큼 순회를 한다 -> n
매번 길이가 n+1인 배열을 새롭게 정의하여 옮겨담는 과정을 거친다 -> n
따라서 이 알고리즘의 시간복잡도는 O(n^2)이 된다.
매 로직의 실행마다 n의 값이 10분의 1씩 줄어든다.
따라서 이 로직의 시간복잡도는 O(logn)이 된다.
mergesort, quicksort는 O(nlogn)의 시간복잡도를 가지고, binarySearch() 는 O(logn) 의 시간복잡도를 가진다.
위의 경우, mergesort 에서 이미 O(blogb)의 시간이 걸리고,
binarySearch() 에서 O(logb) 만큼의 시간이 소요되고, 이를 a번 반복하므로, 결론적으로는 아래와 같은 시간복잡도를 가지게 된다.
O(blogb) + O(alogb)
Last updated
