시간복잡도 = 어떤 프로그램이 소요하는 시간을 나타내는 개념
(시간복잡도) TC = (컴파일 시간)c + (실행 시간) T(n)
통상적인 컴퓨팅 환경에서 공간복잡도가 시간복잡도에 비해 덜 중요하게 여겨지는 이유
-> 기술의 발전으로 메모리 환경이 좋아졌기 때문
BIg - O Notation -> 식을 단순화 하는 것
정의 : n ≥ n0인 모든 n에 대해 f(n) ≤ c · g(n)를 만족하는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n))
1. 가장 중요한 항 이외에는 시간복잡도에서 무시된다.
f(n) = 1000n + 5000
-> 5000은 영향을 주지 못하므로 f(n) = O(1000n)
2. 상수 하나 곱한다고 시간복잡도에 영향을 미칠 수 없다.
-> BIg - O Notation의 정의로부터, 상수항의 곱이 시간복잡도에 영향을 줄 수 없음
3. 일단 최대한 단순화해놓고, 비교하기 편한 것부터 보자
4. n0 하나만 찾으면 되니, n이 한없이 커질 때를 생각하자
-> 2^n 과 n^2 같은 것을 비교할 때 n이 한없이 커질 때를 생각하여 비교
시간복잡도 분석할 때 최악, 최고, 평균
각자 다르게 나올 수 있다.
Brute Force = 가능한 모든 경우를 시도하여, 원하는 답을 찾아내는 알고리즘
전체 case 들을 하나하나 탐색하며, 문제 조건에 부합하는지 판단
-> 직관적이고 적용하기 쉬우나 과정이 매우 느릴 수 있음에 유의
-> 모든게 대입하기 어려운 경우 다른 알고리즘 생각하기