[Algorithm] 시간복잡도 문제

시간복잡도 문제 풀기

주어진 문제 또는 코드에서 시간복잡도를 간단하게 구해보자.

 

문제

• 주어진 두 자연수를 더하기 : 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번