14Dec2019 TIL

Today I learned :

• Time complexity Blogging
• Hash Table implementation in the basic level
• Binary Search Table implementation
• Fixed and submitted previous assignment, .stringifyJSON()

---

 

오늘의 생각 : 

쓰다보니 배운 것을 직접 세부적으로 기록하기 보단, 오늘의 한 일을 적어놓는 곳 같네 ^^;;

밀어놨던 집안일을 한 번에 처리하고, 코딩 과제들을 순차적으로 처리하는 날! 주말이 제일 좋아!!!

어제 그리고 오늘, 집 근처 산책을 40분 동안 했다. 내일도 운동을 갈 수 없으니 산책이라도 해야지!

 

내일은 드디어 한 달만에 재개되는 꽃꽃이 수업. 2시간의 힐링 시간을 보낸 후, 

오늘 페어님의 사정으로 하지 못했던 페어를 내일 오후에 해야지!

 

 

Time Complexity 시간 복잡도

the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
(출처 : 위키 피디아)

시간 복잡도는 특정 알고리즘이 걸리는 시간의 양을 계산한 것이다. 

알고리즘 : 특정 목적을 달성하기 위해 수행하는 일련의 과정

     e.g.) A라는 장소에서 B라는 장소에 도달하기 까지 걸리는 과정

시간 복잡도 : 알고리즘이 실행되는 시간의 양을 묘사 한 것

    e.g.) A -> B 예상 시간 10분

 

 

---

시간 복잡도는 왜 사용되는 것일까?

상황과 목적에 맞는 최적의 알고리즘 / 데이터 구조를 사용하기 위해서다. 

시간 복잡도를 미리 파악함으로써 불필요한 시간/과정 낭비를 방지하는 목적이 있다.

 

시간 복잡도는 알고리즘이 실행되는 시간의 양을 묘사하는 것으로,

어떤 것을 기준으로 하느냐에 따라 크게 세 가지 방법을 주로 사용 된다. 

 

• 최상의 시간 기준 : Big-Ω Notation
• 평균의 시간 기준 : Big-θ Notation
• 최악의 시간 기준 : Big-O Notation

 

이 중에서 보편적으로 사용되는 접근 법은 최악의 시간을 기준으로 하는 Big-O Notation 이다.

 

O(1) : 데이터의 양과 관계 없이 일정한 실행 시간

     e.g.) Array 에서 찾고자 하는 index를 알고 있는 경우

O(log n) : 데이터의 양이 늘어나도 조금씩 실행 시간이 늘어남

     e.g.) Binary search Tree 를 이용하여 내가 원하는 답을 찾는 경우

O(n) : 데이터 양과 최악의 실행 시간이 같은 경우

    e.g.) Tree 구조에서 가장 하단의 맨 오른쪽 value 를 찾는 경우

O(n^2) : 데이터의 증가와 함께 실행 시간이 제곱으로 늘어나는 경우 

    e.g.) 이중 중첩된 for loop 를 사용하는 경우

O(c^n) : 사용 하면 안된다.

 

Big - O 계산법

O(1) : 상수 일 때

O(log n) : 1/2*N 정도 될 때

O(n) : n만 중요. 2n + 3 = O(n), 3n-1  = O(n)

O(n^2) : n^2만 중요 2n^2+ 3n -1 = O(n^2)

 

---

자료 구조의 Big- O 

출처 : https://blog.chulgil.me/algorithm/