반응형
시간복잡도
-
시간복잡도를 표현하자! Big O 표기법Knowledge/Data Structure 2019. 9. 4. 16:42
- 문제의 크기와 조건 알고리즘 문제가 주어졌을 경우 우선 문제의 크기와 조건 고려해야 한다. 예를 들어 '메뉴판에 있는 모든 메뉴를 읽는데 걸리는 시간을 구하라' 라는 문제가 있을 때 메뉴판이 하나뿐이라면 시간은 사람수 N X 메뉴 갯수 M 만큼 걸리겠지만 사람수만큼 메뉴판이 있다고 조건이 바뀌면 메뉴 갯수 M 만큼만 걸릴테니까. 그렇기에 문제가 주어졌을 땐 항상 문제의 크기와 조건을 먼저 보고 방법을 생각해야 한다. - 시간 복잡도 방법을 생각했다면 그 다음 고려해야 할 것은 시간 복잡도이다. 문제 해결 능력을 측정하는 알고리즘 문제 해결에선 특히 시간이 짧을 수록 효율적이라고 본다 그렇기에 문제가 주어졌을 때 떠올린 해결 방법이 최악의 경우 얼마나 시간이 걸릴지를 대문자 O를 사용하는 표기하는 Bi..