[ALGORITHM] 시간복잡도 / 공간복잡도

복잡도 

• 프로그램의 실행이 얼마나 오래 걸리는지, 얼마나 많은 메모리를 사용하는지 

---

시간복잡도

• 알고리즘에 사용되는 연산횟수의 총 횟수
• 절대적인 수행시간이 아닌 연산횟수를 기준으로 측정함
• 연산횟수를 카운팅 할 때 3가지 경우가 있지만 보통 최악의 경우(빅오표기법)을 기준으로 함

---

공간복잡도

• 알고리즘의 메모리 사용량에 대한 분석 결과
• 프로그램을 실행 완료하는데 필요한 저장공간의 양
• 보통 가변공간(실행 중 동적으로 필요한 공간)에 따라서 복잡도가 좌우됨

---

빅오표기법

https://www.tutorialspoint.com/asymptotic-complexity 참고

• 주어진 함수에서 엄밀한 점근적 상한을 나타내는 점근적 표기법
• 가장 증가율이 높은 수식만 남김
• 연산 횟수는 O(1) → O(logn) → O(n) → O(nlogn) → O(n²) → O(2^n) → O(n!) 갈수록 증가함

---

예시

/** 
* 인프런 더개발자, 인터뷰 가이드 참고
* list.contains는 배열을 전체 loop돌아서 찾아서 시간복잡도가 올라감 
* 배열의 갯수만큼 리스트를 만듬 
* 시간 복잡도: O(n) * O(n) => O(n²) 
* 공간 복잡도: O(n)
*/
public int numberSearch(int[] numbers) {
    List<Integer> list = new ArrayList<>();
    for (int number : numbers) {
      if (list.contains(number)) {
        list.remove((Integer) number);
      } else {
        list.add(number);
      }
    }
    return list.get(0);
}