bigO 계산하는 방법 예제

 

몇 가지 예제를 들어 bigO 를 계산해본다.

 

 

문제) 길이를 알 수 없는 문자열에서 각 문자가 유일한지 알아보고 싶다.   예를 들어 "abcdee" 라는 문자열이 있다고 하자. 가장 쉬운 방법으로 2중 for문을 사용하여 i번째 index와 i 이후번째 index를 비교해보는 것이다.   이 때 bigO는 어떻게 될까? 길이가 n 이라고 할 때, 첫번째 for문에서 (n-1)번 돌아간다. 두번째 for문에서 (n-2)번 돌아간다. 세번째 for문에서 (n-3)번 돌아간다. .... 마지막 for문에서 1번 돌아간다. 이를 모두 더하면 n-1 + n-2 + n-3 + ... + 1 이 된다. 등차수열의 합 공식을 사용하면 아래와 같이 된다.   등차수열의 합 공식 따라서 O(n^2) 이 된다.   참고로 등비수열의 합 공식은 아래와 같다. a가 첫째항, n이 항의 개수, r이 공비 등비수열의 합 공식

 

 

문제) 길이를 알 수 없는 단어들로 이루어진 배열의 모든 단어들을 하나의 String 값으로 바꾸고 싶다.   이를테면 ["abc","d","efghi"] 배열이 있다면, "abcdefghi" 하나로 만들고 싶다. 가장 쉬운 방법으로 비어있는 String 객체 하나를 준비한 다음 뒤에 덧붙여나가면 된다. 이를테면   String result = ""; for( String s : array){     result+=s; }   이 때의 bigO 값은 어떻게 될까? 모든 단어들의 길이를 x라고 가정해보자. 단어를 뒤에 덧붙일때마다 새로운 String 객체가 만들어지고 그 길이만큼 복사가 이루어진다.   첫번째 for문에서 x 번 복사된다. 두번째 for문에서 2x 번 복사된다. (기존의 x와 새로운 x) 세번째 for문에서 3x 번 복사된다. (기존의 2x와 새로운 x) .... 마지막 for문에서 nx 번 복사된다. 이를 모두 더하면 (1+2+...+n)x 가 되고 등차수열의 합 공식에 의해 O(n^2*x) 가 된다.