일상 적인 코드 속 빅 오

여러 코드를 보고 빅 오를 판단 해보자.

짝수의 평균

public class evenNumberAvg {
    public static void main(String[] args) {
        double sum = 0;
        int cntEvenNumber = 0;
        int[] arr = new int[20];
        for(int i = 0; i < arr.length; i++){
            if(arr[i] % 2 == 0) {
                sum += arr[i];
                cntEvenNumber += 1;
            }
        }
        System.out.println(sum/cntEvenNumber);
    }
}

이 코드는 배열의 크기를 N으로 입력 받는다. 또한 반복문은 N번 만큼 동작한다. 반복문 내에서 짝 수 인지 확인하고, 짝수라면 sum에 더하고 짝수의 수를 카운트한다. 즉 반복문 밖에서 일어나는 3번의 단계와 반복문 내에서 일어나는 3번의 단계가 필요로 한다. 따라서 3N + 3의 단계를 필요로 하지만 빅 오는 O(N)이다.

단어 생성기

public class wordGenerator {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        ArrayList<String> arrayList2 = new ArrayList<>();
        for(int i = 0; i < arrayList.size()-1; i++){
            for (int j = i + 1; j < arrayList.size(); j++){
                arrayList2.add(arrayList.get(i) + arrayList2.get(j));
            }
        }
        System.out.println(arrayList2);
    }
}

이 코드는 배열에 모든 알파벳을 더 해 두 글자로 만든다. 즉 입력 크기는 배열의 크기인 N이다.
그리고 이 코드는 (N-1) + (N-2)...+1 단계를 필요로한다.
빅 오는 상수와 낮은 차수를 고려하지 않는다. 따라서 이 코드의 빅 오는 O(N^2)이다.
만약 알파벳의 길이를 3으로 조합하는 코드의 빅오는 얼마일까??
O(N^3)이다.

배열 예제

이 코드는 배열이 주어진다면 배열의 첫번째, 마지막, 중간 값을 반환하는 코드이다.
따라서 3 단계를 필요로 하고 이를 표현하면 O(1)이다.

평균 섭씨 온도 구하기.

public static void avgCelsius(double[] arr){
        double[] arr2 = new double[arr.length];
        for(int i = 0; i < arr.length; i++){
            arr2[i] = (arr[i]-32)/1.8;
        }
        double sum = 0;
        for(int i = 0; i < arr2.length; i++){
            sum += arr2[i];
        }
        System.out.println(sum/arr2.length);
    }

이 코드는 주어진 배열의 온도를 섭씨로 변환해서 배열에 추가하고 그 후 섭씨 배열의 값을 더해서 총 온도를 구한 후 평균을 출력한다. 섭씨 변환 N 총 합 N 그 따 3 즉 2N + 3 단계가 걸린다.
하지만 빅 오는 상수를 무시한다. O(N)이 걸린다.

의료 상표

    public static String[] markInventory(String[] arr){
        String[] arr2 = new String[arr.length];
        for(int i = 0; i < arr.length; i++){
            for(int j = 1; j < 6; j++){
                arr[j] = arr[i] + j;
            }
        }
        return arr2;
    }

옷 아이템의 개 수는 변화 하지만, 사이즈는 1~5로 고정되어 있다. 즉 5N만큼 동작한다.
따라서 빅 오는 O(N)이다.

1 세기

    public static void count(int[][] arr){
        int cnt = 0;
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr[i].length; j++){
                if(arr[i][j] == 1) cnt +=1;
            }
        }
        System.out.println(cnt);
    }

이 코드는 이차원 배열이 주어진다면, 치 아원 배열의 존재하는 1의 수를 카운트 하는 코드이다.
이 차원 배열의 크기가 같을 경우 N^2이지만, 배열의 크기가 다르다면 M * N 단계가 필요하다.
즉 이 코드의 빅 오는 배열의 크키에 따라 O(N) 혹은 O(N^2)이다.

팰린드롬 검사기

    public static Boolean isPalindrome(String[] arr){
        int leftIndex = 0;
        int rightIndex = arr.length;
        while (leftIndex < arr.length/2){
            if(arr[leftIndex] != arr[rightIndex]) return false;
            leftIndex++;
            rightIndex--;
        }
        return true;
    }

이 코드는 배열의 크기인 N의 절반만큼 단계를 수행한다. 빅 오는 상수를 무시하기에 O(N)이다.

모든 곱 구하기

    public static ArrayList<Integer> twoNumberProducts(int[] arr){
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < arr.length - 1; i++){
            for(int j = i + 1; j < arr.length; j++){
                arrayList.add(arr[i] * arr[j]);
            }
        }
        return arrayList;
    }

배열 크기 N의 관점으로 보면 (N-1) + (N-2)....+1번 실행된다. 이 공식은 항상 N^2/2로 계산된다. 따라서 O(N^2)이다.

암호 크래커

def every_password(n)
  (("a" * n)..("z" * n)).each do |str|
    puts str
  end
end

• 변수 n으로 쓰일 수를 전달하면 해당 길이의 모든 알파벳의 조합을 리턴하는 함수로 n이 3이라면 'aaa', 'aab', 'aac' ... 'zzy', 'zzz'를 출력한다.
• N의 관점에서 보면 총 조합의 수는 26N으로 N이 1씩 늘어날때 마다 단계수는 26배씩 늘어나는 비효율적인 알고리즘이다.