- O(1)
- 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
- O(n)
- 입력 데이터의 크기에 비례하여 시간이 걸리는 알고리즘
- for문
- 입력 데이터의 크기에 비례하여 시간이 걸리는 알고리즘
- O(n^2)
- O(n) 안에서 또 루프를 돌려서 O(n)으로 돌아가는 알고리즘
- 2중 for문
- O(n) 안에서 또 루프를 돌려서 O(n)으로 돌아가는 알고리즘
- O(n^m)
- O(n) 안에서 m개만큼 다중 O(n)이 돌아가는 알고리즘
- m중 for문
- O(n) 안에서 m개만큼 다중 O(n)이 돌아가는 알고리즘
- O(2^n)
- 피보나치 수열
- 사각형을 그려나가면서 면적이 가장큰 부분이 정사각형으로 늘어남
- ex) 1일때는 1칸이 늘어나고 이렇게 늘어나서 사각형중 면적이 가장큰 3으로 늘어나고 점점 늘어난다.
- 사각형을 그려나가면서 면적이 가장큰 부분이 정사각형으로 늘어남
- 매번 함수가 호출될떄마다 두번씩 추가로 호출됨
- 이게 트리의 높이만큼 반복됨
- 피보나치 수열
- O(m^n)
- 2개가 아닌 m개씩 추가로 호출
- O(log n)
- 이진트리
- 가운데 값을 찾아서 키값과 비교함 키값이 더 클경우 앞에 데이터들은 안보고 뒤에있는 데이터를 기준으로 중간을 찾아 그 중간을 비교함
- 작을경우 뒤를버리고 앞으로감
- 조회할때마다 조회해야할 데이터의 양이 절반씩 떨어지는 알고리즘
- 이진트리
- O(sqrt(N))
- n개의 아이템을 정사각형에 채우고 가장 윗줄이 sqrt(N)
- 9일경우
- 1,2,3
- 4,5,6
- 7,8,9
- 이므로 9의 sqrt(N)은 3이다.
- 9일경우
- n개의 아이템을 정사각형에 채우고 가장 윗줄이 sqrt(N)
- Big O에서 상수는 과감하게 버린다.
- O(2n) ⇒ O(n) 으로 표기한다.
출처
https://www.youtube.com/watchv=6Iq5iMCVsXA&ab_channel=%EC%97%94%EC%A7%80%EB%8B%88%EC%96%B4%EB%8C%80%ED%95%9C%EB%AF%BC%EA%B5%AD