알고리즘 복잡도

BIG O 표기법

O(n), O(logN), O(1), O(n2)

• 주어진 함수에서 엄밀한 점근적 상한을 나타내는 점근적 표기법
• 숫자는 다 빼기
• 가장 증가율이 높은 수식만 남기기

함수의 복잡도

• f(n) = 4텍스트
• f(n) = 2n+3
• f(n) = 3n2 + n + 5
• f(n) = 4n + log(n) + 3

코드의 시간과 공간 복잡도

예제1

boolean isFirstTwoMatch(int[] elements) {
    return elements[0] == elements[1];
}

시간복잡도 : O(1)
공간복잡도 : O(1)

예제2

int sum(int[] elements) {
    int sum = 0;
    for(int number : elements) {
        sum += number;
    }
    return sum;
}

시간 복잡도 : O(n)
공간 복잡도 : O(1)

예제3

int factorial(int number) {
    if (number <= 2) {
        return number;
    }
    return number * factorial(number - 1);
}

시간 복잡도 : O(n)
공간 복잡도 : O(n)

예제4

int findNumber(int numberToFind, int[] sortedNumbers) {
    int low = 0;
    int high = sortedNumbers.length - 1;
    int index = 0;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        int midNumber = sortedNumbers[mid];
        if (midNumber < numberToFind) {
            low = mid + 1;
        } else if (midNumber > numberToFind) {
            high = mid - 1;
        } else if (midNumber == numberToFind) {
            index = mid;
            break;
        }
    }
    return sortedNumbers[index];
}

시간 복잡도 : O(logN)
공간 복잡도 : O(1)

유일한 숫자 찾기

numbers라는 int형 배열이 있다.
해당 배열에 들어있는 숫자들은 오직 한 숫자를 제외하고는 모두 두번씩 들어있다.
오직 한번만 등장하는 숫자를 찾는 코드를 작성해라.

방법1

List를 만들고 배열에 있는 숫자를 순회하면서 해당 숫자가 List에 들어있는지 체크한다.
List에 들어있으면 List에서 빼내고 없으면 넣는다.

private int solution1(int[] numbers) {
    List<Integer> list = new ArrayList<>();
    for (int num : numbers) {
        if (list.contains(num)) {
            list.remove((Integer) num);
        } else {
            list.add(num);
        }
    }
    return list.get(0);
}

시간 복잡도 : O(n2)
공간 복잡도 : O(n)

방법2

HashMap을 사용해서 배열에 들어있는 숫자를 키, 숫자의 등장 횟수를 Value로 등록한다.
숫자의 등장 횟수가 1인 키 값을 찾아서 리턴한다.

private int solution2(int[] numbers) {
    HashMap<Integer, Integer> numbersMap = new HashMap<>();
    
    for (int num : numbers) {
        numberMap.put(num, numbersMap.getOrDefault(num, 0) + 1;
    }
    
    for (int num : numbers) {
        if (numbersMap.get(num) == 1) {
            return num;
        }
    }
    
    return 0;
}

시간 복잡도 : O(n)
공간 복잡도 : O(n)