🖥 Computer Science/알고리즘

🧐 곱하기 알고리즘 성능 분석 우리가 흔히 곱하기 계산을 할 때 사용하는 방법을 통해 n-bit 이진수 곱하기 알고리즘의 시간 복잡도를 구해보도록 하겠습니다. 우선 일반적인 계산 과정은 아래와 같습니다. 곱하기의 계산에서는 곱하는 수(y)의 각 bit에 대하여, 이동 연산(주항색 화살표로 표시)을 진행하게 됩니다. 첫 과정에서는 0번, 두번째 과정에서는 1번, 세번째 과정에서는 2번, .... n번째 과정에서는 n-1번의 이동 연산이 필요합니다. 즉 이를 빅오 표기법을 통해 나타내면 다음과 같습니다. $$O(1) + O(2) + \cdots + O(n-1) = O(n^{2})$$ 이동 연산을 모두 진행한 후에는, 최대 2n bit로 이루어진 숫자 n개에 대하여 add 연산을 진행해야 합니다. 이때 한번의..

🧐 알고리즘? 어떤 문제를 풀기 위한 유한한 절차와 방법을 의미합니다. 위 정의에서의 '문제'는 보통 입력값이 동일한 경우 출력값이 동일한(= 수학적으로 엄밀히 정의된) 문제를 의미합니다. 절차와 방법? 저희는 계산 문제를 풀 때 숫자와 사칙연산을 이용하여 문제를 풀이하는 것 처럼 컴퓨터로 계산 문제를 풀기 위해서는 컴퓨터에 주어진 명령어 집합(instruction set)을 이용하여 풀이합니다. 🧐 알고리즘의 성능 분석 알고리즘의 성능을 분석하는 방법으로는 실제로 시작시간과 종료시간을 측정하여 분석하는 실험적 분석과, 이론적으로 기술하여 성능을 측정하는 이론적 분석 방법이 있습니다. 실험적 분석은 때때로 유용하지만, 다양한 외부 요인들(예를 들어, 컴퓨터의 하드웨어 사양)에 의해 성능을 정확하게 분석할..