본문 바로가기

CS/알고리즘

(2)

Boyer-Moore 과반수 투표 알고리즘 Boyer-Moore 과반수 투표 알고리즘 (Boyer-Moore majority vote algorithm)주어진 후보자 목록에서 과반수를 차지하는 후보를 찾는 알고리즘이다.배열 내 과반수에 해당하는 원소가 항상 존재한다고 가정하면, 결과값은 항상 과반수 원소가 된다.핵심 아이디어는 주어진 후보자 목록에 두 가지의 서로 다른 후보를 지정하고, 이들을 서로 상쇄시켜가며 최종 후보를 결정하는 것이다.시간 복잡도는 O(N), 공간 복잡도는 O(1) 이다. 동작 방식 입력 시퀀스 요소 m과 카운터 c를 0으로 초기화한다.입력 시퀀스에서 각각의 요소 x에 대해서c == 0 이면 m = x, c = 1 대입한다.m == x 이면 c = c + 1 대입한다.m != x 이면 c = c -1 대입한다.m을 반환한다...

알고리즘 복잡도 시간 복잡도 & 공간 복잡도 알고리즘의 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 최근에는 하드웨어 메모리 용량이 커졌기 때문에, 알고리즘 성능 측정에서는 시간 복잡도가 좀 더 우선시된다. 1. 시간 복잡도알고리즘에 필요한 단계 수만 고려한다.데이터가 증가할수록 단계 수가 어떻게 변하는지를 말해준다.2. 공간복잡도프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양이다.정적으로 선언된 변수, 재귀함수와 같이 동적으로 공간을 계속해서 필요로 하는 경우도 포함한다. 빅 오 표기법자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 등장했다.절대적인 실행 시간과 필요한 자원 공간의 양을 파악하기란 어려우므로, 빅 오 표기법으로 알고리즘의 효율성을 정량화할 수 있다.입력 크기 N에 따라 연산이..

티스토리툴바