200908_TIL

Today I learned

• Complexity Analysis
• Time complexity

@@ 오늘은 시간 복잡도 및 공간 복잡도, 복잡도 분석에 대해 추가적으로 더 학습했다. 스프린트 진행하며 복잡도에 대해서 배웠던 부분을 정리했다.

그동안 몰랐던 빅오 표기법, 빅 오메가, 빅 세타 등에 대해서도 배울 수 있었고, 자료구조를 배우는 이유, 그리고 자료구조들의 시간 및 공간 복잡도, 실 사용의 예에 대해서 되짚어 보았다.
항상 공부를 할 땐 내가 이것을 왜 배우는가 알지 못하면 마냥 어렵게만 느껴지지만, 왜 이것이 필요한지를 알면 공유할 때 동기부여도 되고 좀 더 효율적으로 학습하게 되는 것 같다. 그런 의미로 오늘 스프린트를 정리할 수 있는 오피스아워, 스프린트 리뷰시간이 기억에 남고 도움이 많이 됐다.

빅오 표기법을 배우며 알고리즘의 시간 복잡도를 수학적으로 연산하는 것과 그래프의 전위 순회, 중위 순회 등을 수학적으로 풀이하는 것도 새롭게 학습했는데 많이 접해보지 못했던 것이 수학적으로 쉽게 풀리는 것을 보고 정말 신기했고, 수학 및 연산을 다시 많이 접해봐야겠다. 수학적 사고를 많이 익혀야겠다는 생각을 했다.

너무 좋은 레퍼런스들이 쏟아진다. 블로그를 정리하며 함께 보고 정리해나가야겠다.

오늘은 우분투가 네트워크와 오디오가 자꾸 말썽이라 default 설정값을 바꾸기 위해 고군분투 했었는데, 결국 네트워크는 dns를 다시 잡아줘서 속도 개선이 어느정도 됐지만 오디오값은 스택오버플로우를 보면서 설정값을 바꿔봐도 default값이 바뀌지 않아서 1시간 정도를 그냥 버렸다. 우선은 매번 컴퓨터를 켜서 설정을 바꿔주는 수밖에 없겠지만 그래도 나중에 다시 시도해봐야겠다.

Complexity analysis

• 알고리즘 풀이에 대해 시간과 공간을 얼마나 차지하는지 나타내는 지표

• 왜 중요한가?

  • 알고리즘의 효율성
  • 모든 경우의 수를 다 포함하려면 시간과 공간이 굉장히 많이 필요로 하기 때문이다.

• 알고리즘 로직이 원하는 결과에 도출하면, 그 다음은 알고리즘의 효율성, 복잡도를 고려해야한다.

• 알고리즘 : 문제를 푸는 해답
  - 문제 알고리즘이 복잡할 수록 시스템 구동 소요시간은 늘어난다 (시간 복잡도 증가)

• 2 에서 16 사이 두 수의 차이 중 가장 큰 차를 알고 싶을 때
  1. 단순하게는 그냥 모든 경우의 수를 알아보면 된다 (모든 수의 차) (n^2)
  2. 가장 큰수와 가장 작은 수를 확인 한다. (2n)
  3. 정렬된 배열이기때문에 마지막 요소와 첫번째 요소를 뺀 결과를 반환한다 (3)
  3 -> constant time (최고로 빠른 시간복잡도)

  big - O notation (big O 표기법)

  • 최악의 경우를 표현한다

  • 상수와 계수를 제거한다

    ex) 3→O(1) , 2n → O(n), n^2 → O(n^2)

  • 복잡도 순서

    • O(1) → O (logN) → O(n) → O(n^2) → O(c^n)

    • O(1) - constant

      • 배열에서 인덱스 찾기
      • 해쉬테이블에서 요소 찾기

    • O(logN) - logarithmic

      • binary search 평균 복잡도

    • O(n) - linear

      • array에서 값 찾는 것
      • 연결리스트에서 값을 찾는 것

    • O(n^2) - quadratic

      • 중첩 for문

    • O(c^2) - exponential

      • recursion (피보나치)

Data structure with Time complexity

• Array

  • 자바스크립트가 아닌 다른 배열에선 메모리 상에서 사이즈가 정해져있다.

  • primitive data structure

  • Array 아래 있는 것은 object정도밖에 없다.

  • 시간복잡도

    • 인덱스 조회 O(1)
    • 재할당 O(1)
    • 데이터 추가 삭제 O(n)
    • find(value) 값조회 - O(n)

• Linked Lists

  • non-contiguous data structure
  • 가비지 콜렉터 언어인 자바스크립트의 경우 연결 리스트엔 연결이 끊어지면 가비지 콜렉터가 수거해가고, 값이 삭제됐다고 본다.
  • 시간 복잡도
    • Lookup - O(n)
    • find(value) - O(n)
    • assign - O(n)
    • insert - O(1) -> 단순히 제거만 한다고 볼 때, 원래는 찾아서 삭제해야하기때문에 O(n)
    • remove
      • head - O(1)
      • middle - O(n)
      • remove 역시 찾아서 삭제해야 하므로 head를 제외하고는 O(n)

• Doubly - Linked Lists
  - previous node를 알 수 있다.
  - 시간 복잡도
  - Lookup - O(n)
  - find(value) - O(n)
  - assign - O(n)
  - insert - O(1)
  - 이것도 역시 찾아서 해야하므로 O(n) 복잡도를 가진다.
  - remove - O(1)
  - 위와 같이 O(n)의 복잡도를 가진다.

  • tradeoff
    이중 연결 리스트는 공간복잡도를 조금 더 차지한다.

• Tree

  • 내 값과children 값을 갖고 있다.
  • 시간 복잡도
    • Find - O(n)

• Binary Search Tree

  • 시간복잡도
    • Find - O(logN)
  • 최악의 경우 degenerate binary tree 일경우 복잡도는 O(n)
  • 높이가 1이상 차이 나지 않을 경우 balanced binary tree 라 부른다.
  • 추가할 때마다 밸런스를 확인하고 밸런스에 맞게끔 조정해주게 된다면 시간 복잡도가 O(logN)으로 조정시킬 수 있다.

• Binary Search

  • 정렬된 배열보다 BST는 non - contiguous memory를 차지하기 때문에 요소 삭제나 추가시 좀더 효율적이다.