• Big-O 개념에 대해서 다시 공부했다. 알고리즘 공부를 할 때 내가 만든 알고리즘이 효율적인지 아닌지에 대해서 간과했었는데 바보 같은 짓이였다.
    시간 복잡도는 코드가 어떤 의미인지 또는 코드가 몇 번 반복 되는지 생각해보면 된다.
void printUnordered(int[] array){
 for(int i=0 ; i<array.length; i++){
  for(int j= i+1; j<array.length, j++){
    System.out.println(array[i] + ',' + array[j]);
  }
 }
}

위 코드의 시간복잡도를 계산해보자.

  • 코드가 어떤 의미인지 생각해보자.
    j는 항상 i보다 큰 상태로 루프를 돈다. 총 array의 크기가 N이라고 했을 때 i와 j는 총 N^2개의 쌍을 만든다. 이 경우는 항상 j는 i보다 큰 상황이므로 N^2/2 개의 쌍을 만든다. 시간 복잡도를 계산할 때 상수항은 제외하므로 답은 O(N^2)이다.

  • 또는 코드가 몇 번 반복되는지 생각해보자.
    j는 처음 루프에서는 N-1번 반복, 그 다음은 N-2,N-3....1 횟수로 반복한다. 이는 1부터 N-1의 합으로 나타낼 수 있고 N(N-1)/2이다. 시간복잡도는 상수항은 무시하고(여기서는 1/2) 지배적이지 않은 항은 무시하므로 답은 O(N^2)이다.

[출처 : 코딩인터뷰 완전 분석]

  • 이 책에 있는 첫 문제부터 이해가 안간다. 큰일이야 정말
  • 반면 자바스크립트의 클로저의 개념에 대해서는 이해가 가기 시작했다. 어떻게 사용되고 있는지 좀 더 살펴봐야할 거 같다.