Java로 보는 시간복잡도, 공간복잡도

https://www.youtube.com/watch?v=9MMKsrvRiw4&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=2 

 

 

문제 1 - O(N)

N이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라.

N은 10만 이하의 자연수 이다.

func1(16)=60

public class Main {

    public int solution(int num) {
        int ret = 0;
        for (int i = 1; i <= num; i ++) {
            if( i % 3 == 0 || i % 5 == 0) ret += i;
        }
        return ret;
    }

    public static void main(String[] args) {
        Main T = new Main();
        int num = 16;
        System.out.println(T.solution(num));
    }
}

 

문제 2 - O(N²)

주어진 길이의 N의 int배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을,

존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라.

arr의 각 수는 0 이상 100이하 이고, N은 1000이하이다.

 

func2({1, 52, 48},4) = 1

public class Main {

    public int solution(int[] numArray, int num) {
        int answer = 0;

        for (int i = 0; i < num ; i++) {
            for (int j = 0; j < num; j++) {
                if (numArray[i] + numArray[j] == 100) return 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        int[] numArray = {1, 52, 48};
        int num = 3;
        System.out.println(T.solution(numArray, num));
    }
}

 

문제 3 - O(√N)

N이 제곱수이면 1을 반환하고, 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.

func3(9) = 1

public class Main {

    public int solution(int num) {
        // i가 1부터 올라가면서 1의 제곱이 N과 일치하는지 확인
        // 2의 제곱이 N과 일치하는지 확인하고,
        // 계속 가다가 N과 일치하는 순간이 있으먄 N이 제곱수이니 1을 반환
        for (int i = 1; i*i <= num; i++) {
            if(i*i == num) return 1;
        }
        // 일치하는 순가이 없이 i의 제곱이 N보다 커져 for문을 탈출하게 되었다면 제곱 수가 아니니 0을 반환
        return 0;
    }

    public static void main(String[] args) {
        Main T = new Main();
        int num = 9;
        System.out.println(T.solution(num));
    }
}

 

문제 4 - O(lgN)

N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(Int N)을 작성하라.

N은 10억이하의 자연수이다.

func4(5) = 4

public class Main {

    public int solution(int num) {
        // 2의 거듭제곱이 저장되는 변수
        int val = 1;
        // 맨처음에 1,2,4,8,,, 이렇게 커지다가 val을 2배했을 때 N보다 커지게 되는 순간에 while 탈출
        while (2*val <= num) val *= 2;
        return val;
    }

    public static void main(String[] args) {
        Main T = new Main();
        int num = 5;
        System.out.println(T.solution(num));
    }
}

• N이 2^k이상 2^K+1 미만이라고 할때 while문 안에서 val은 최대 k번만 2배로 커진다
• 그러고 나면 val은 2^k가 되고, 이후 2*val <= N이 거짓이 된다
• 로그의 정의에 입각해서 생각할 때는 k는 logN이니 결국 시간복잡도는 O(logN)이 된다.