chapter1-2

일반적으로 Time-complexity가 polynomial이면 efficient하다고 하고, Exponential이면 inefficient하다고 정의한다. 하지만 실제로는 cubic만 되도 Time-complexity가 엄청 늘어나므로 실질적으로는 거리가 멀다.

---

Worst-Case versus Average-Case Time Complexity

Worst-case complexity란 말 그대로 모든 경우가 다 일어나고 끝나는 경우이다. 

Average-case complexity는 평균적으로 걸리는 시간 복잡도이다.

Quick sort를 예로 들자면, Worst-case complexity는 O(n^2)이고 Average-case complexity는 O(nlogn)이다

g(n)은 이해하였으니 넘어가도록 하고 밑에 ex를 보면 ex1은 g(n)이 n에 종속되지 않기 때문에 O(1)이고

---

Reviews - Run Time Analysis

 

---

최대 부분 수열의 합 문제

최대 부분 수열의 합 문제이다. 백준 1912번 연속합 문제와 똑같은 문제이다. DP로 해결하면 O(n)에 해결이 가능한다. 하지만 본 수업에서는 더 심도있게 이 알고리즘을 다루고자 한다.

위 알고리즘은 O(n^3)에 최대 부분 수열의 합을 구하는 식이다.

0에서 부터 N-1까지 개수가 1,2,...,N개의 합을 구한다. 그리고 1부터 N-1까지 개수가 1,2,...,N-1개의 합을 구한다. 이를 N-1일 때까지 반복하는 것이다. 위에 시간 복잡도를 구하는 것을 보면 시간 복잡도가 O(N^3)이 나오는 것을 알 수 있다. 솔직히 이렇게 구하려고 생각하는게 더 힘든 거 같다...

위 알고리즘은 i를 1씩 증가시키면서 i번째 부터 N번째 까지 더하면서 최대값일 경우 값을 갱신해주는 알고리즘이다.