시간복잡도 문제 풀기
주어진 문제 또는 코드에서 시간복잡도를 간단하게 구해보자.
문제
- 주어진 두 자연수를 더하기 : 3번 ~ 4번
- 1부터 N까지 2의 배수를 찾기 : N번 이상
- 책을 꺼내는데 1초의 시간이 소요된다. 원하는 책을 찾는 데 걸리는 시간 : N초
- 책에 번호가 붙여져 있고, 순서대로 꼳혀있는 경우 찾는 데 걸리는 시간 : log N초
- 주어진 숫자들을 정렬하기 : NlogN번
- 주어진 숫자들에서 서로 다른 위치의 요소 합이 특정 값이 되는 경우의 수 구하기 : N번
- 주어진 수가 제곱수인지 구하기 : logN번
- 1~N까지 수 중에서 가장 큰 2의 거듭제곱 수 구하기 : logN번
코드
public static int N;
public static int nums[];
public static boolean visited[];
static void solve(int depth) {
if(depth>N) {
System.out.println(Arrays.toString(num));
return;
}
for(int i=1; i<=N; i++) {
if(!visited[i]) {
num[depth] = i;
visited[i] = true;
solve(depth+1);
visited[i] = false;
}
}
}
public static void main(String[] args) {
N = 8;
nums = new int[N+1];
visited = new boolean[N+1];
solve(1);
}
: N!번
public static void main(String[] args) {
int N = 10;
int target = 8;
int nums[] = new int[N+1];
for(int i=1; i<=N; i++) {
nums[i] = i;
}
Arrays.sort(nums);
left = 1;
right = N;
answer = -1;
while(left<=right) {
mid = (left+right)/2;
if(nums[mid]==target) {
answer = mid;
}
else if(nums[mid]>target) {
right = mid-1;
}
else {
left = mid+1;
}
}
}
: NlogN번
'Computer Science > Algorithm' 카테고리의 다른 글
[Algorithm] 완전탐색 - 부분집합 (0) | 2023.08.08 |
---|---|
[Algorithm] 완전탐색 - 조합 (0) | 2023.08.08 |
[Algorithm] 완전탐색 - 순열 (0) | 2023.08.08 |
[Algorithm] 알고리즘 성능 (0) | 2023.08.08 |
[Algorithm] 알고리즘 기초 (0) | 2023.08.07 |