[Java/Algorithm]복잡도 Complexity

 

복잡도
Complexity
: 알고리즘의 성능을 객관편으로 평가하는 기준.

1. 시간 복잡도 Time Complexity
   : 실행에 필요한 시간을 평가하는 것.
2. 공간 복잡도 Space Complexity
   :  기억 영역과 파일 공간이 얼마나 필요한가.

---

선형 검색의 시간 복잡도

※ 복잡도를 표기할 때 사용하는 O는 Order의 앞글자 입니다.

• 한번만 실행하는 경우 복잡도는 O(1) 로 표기합니다.
  int i = 0;
  return문
• 반복문의 평균 실행 횟수는 n/2입니다.
  이 경우 O(n)으로 표기합니다.

※ 컴퓨터에서는 n/2와 n의 차이가 크지 않아 위와 같이 표기합니다.

• 위 와 같은 선형 알고리즘의 복잡도를 계산해보면 이와 같습니다.
  O(1) + O(1) + O(n) + O(n) + O(n) + O(1) = O(max(1, 1, n, n, n, 1)) = O(n)
• 자세히 설명하자면
  int i = 0;O(1) + a[n] = k;O(1) + while(true)O(n) + if(a[i] == k)O(n) + i++;O(n) + return i == n?O(1) 
  를 순서대로 적은 것입니다.
  여기서 max() 함수를 이용해 가장 큰 값을 찾아냅니다.
• 따라서 선형 검색의 복잡도는 O(n)입니다.

---

 

※ 선형검색에서 for문이 하나 일 때 O(n)이기 때문에 2중for문의 복잡도는 O(n²)이 됩니다.

※ 이진검색의 복잡도는 계속해서 반으로 나누기 때문에 O(log n)입니다.

---

문제풀이

이번에 짠 코드는 좀 맘에 듭니다.