728x90 반응형 Computer Science/알고리즘8 알고리즘 성능 측정의 지표 - 빅오 표기법(Big-O Notation) 빅오 표기법 알고리즘의 성능을 측정하기 위한 가장 중요한 지표로 빅오 표기법이 존재한다. 빅오 표기법으로 시간 복잡도와 공간 복잡도를 계산할 수 있는데, 우선 빅오 표기법이 뭔지부터 알아보자. 위의 그래프가 빅오 표기법을 나타낸 그래프이다. 빅오 표기법은 크게 아래의 7가지로 나눌 수 있다. O(1) O(logN) O(N) O(NlogN) O(N^2) O(N^3) O(2^N) 빅오 표기법이란 간단히 설명해서 O() 괄호 안에 원하는 식을 집어 넣는다. 그리고 식의 계수는 다 떼어 버린다. 왜냐하면 10000000000N이 아무리 크다 하더라도 N이 극한에 가까워지게 되면 결국 N^2보다 작아지는 순간이 오기 때문이다! 그렇게 해서 어떤 식이 더 규모가 큰 식인지를 빅오 표기법으로 구분하는 것이다. O(1.. 2023. 5. 18. 완전탐색(Brute Force)과 백트래킹(Backtracking)의 차이 완전탐색(Brute Force) 1) 탐색 순서 브루트포스는 가능한 모든 해를 순차적으로 검사하는 방식이다. 모든 경우의 수를 하나씩 시도하여 정답을 찾을 때까지 모든 경우를 확인한다. 즉, 문제 공간의 모든 가능성을 전부 조사하는 방식이다. 2) 제약 조건 브루트포스는 문제의 제약 조건을 고려하지 않고 모든 가능한 해를 탐색한다. 제약 조건에 따라 해의 개수가 많아질 수 있다. 3) 탐색 중단 브루트포스는 모든 가능한 해를 탐색해야 하므로, 정답을 찾지 못하더라도 모든 경우를 검사한다. 따라서 실행 시간이 길어질 수 있다. 백트래킹(Backtracking) 1) 탐색 순서 백트래킹은 탐색 도중 불필요한 부분을 가지치기하여 탐색 공간을 줄인다. 유망한 후보 해를 따라가다가 더 이상 진행할 수 없는 상황에.. 2023. 5. 17. 이전 1 2 다음 728x90 반응형
