UPO/7회

UPO 7회차 문제의 주제는, 밀레니엄 문제 중 하나인 P-NP 문제입니다. (괴수가 한 분 나타나셔서 난이도를 많이 높였습니다.)

1일차 문제는 주제 자체가 어려운 만큼 난이도를 쉽게 냈습니다.

2일차 문제는 조금 어렵습니다.

• 돌아가기

1일차 문제

지문

1일차 문제의 주제는 알고리즘과 시간 복잡도이다. 모두 처음 들어 보는 말일 것이다. 한번 차근차근 따져 보자.

알고리즘(Algorithm)은 기본적으로 문제를 해결하기 위한 절차나 방법을 의미한다. 컴퓨터가 일을 수행하기 위해서는 그 방법을 알고 있어야 한다. 그러나 인공지능이 아닌 이상 컴퓨터는 스스로 그 방법을 찾아내기 어렵다. 따라서 프로그램을 만드는 사람이 그 방법을 알려 주어야 한다. 똑같은 문제를 해결하기 위해서는 여러 가지 방법이 있을 수 있는데, 그 중 가장 효율적인 방법(주로 시간이 짧게 걸리는 방법이나, 적은 메모리를 사용하는 방법)을 찾아야 한다. 컴퓨터의 계산 속도는 매우 빠르지만, 계산량이 많아지면 컴퓨터가 계산하는 데 걸리는 시간도 자연스럽게 늘어난다. 이것을 연구하는 과정에서 알고리즘에 관한 연구가 발전하였다.

우리 주변에도 다양한 알고리즘이 사용되고 있다. 대표적인 예시로 길을 찾아주는 내비게이션을 들 수 있다. 내비게이션은 빠른 시간 안에 경로를 찾아 주는데, 가능한 모든 경로를 다 시도해 본 뒤 가장 빠른 경로를 찾는 방법은 상식적으로도 너무 긴 시간이 걸릴 것이다. 이때 내비게이션은 다익스트라(Dijkstra)나 에이 스타(A*) 알고리즘 등을 사용해 경로를 빠른 시간 안에 찾는데, 이것은 어려우므로 여기서는 그냥 넘어가자.

시간 복잡도(Time Complexity)는 알고리즘을 수행하는 데 걸리는 시간을 대략적으로 나타낸 것이다. 시간 복잡도를 표기할 때 우리는 주로 점근 표기법을 사용한다. 예시를 들어 보자.

N명의 학생이 있고, 학생들의 키를 알고 있다. 가장 키가 큰 학생의 키를 어떻게 하면 알아낼 수 있을까? 아래와 같은 방법으로 알아낼 수 있다.

1. 우리가 구하고자 하는 답을 저장할 변수 answer를 만든 뒤, answer에 0을 넣는다. (모든 키는 0보다 크기 때문이다.)
2. 첫 번째 학생부터 마지막 학생까지 각각의 키를 살펴본 뒤, 그 키가 answer보다 크면 answer를 그 학생의 키로 바꾼다.
3. 이 과정을 마치고 나면, answer에는 가장 키가 큰 학생의 키가 담겨 있을 것이다.

이 과정에서 우리는 총 몇 번의 계산을 하게 될까?

1. answer 변수를 만든다. (1회)
2. answer 변수에 0을 넣는다. (1회)
3. 각 학생의 키를 answer와 비교한다. (N회)
4. 키가 answer보다 크면, answer에 키를 넣는다. (최소 1회~최대 N회)

위는 대략적으로 추산한 것으로, 정확한 수치는 아니지만, 우리는 대략 N회 ~ 2N회 사이의 연산이 필요함을 알 수 있다. 이때 N 앞의 상수(계수)를 없애고 나면, 시간 복잡도는 N이라는 사실을 알 수 있다. 우리는 이것을

$O(N)$

과 같이 표기한다.

시간 복잡도를 표기할 때 조심해야 될 것이 몇 가지 있다. 먼저, 문제를 풀기 위해 필요한 연산의 수가 $5N^{2}+10N+6$라고 하자. 이때 우리는 가장 차수가 큰 것만 시간 복잡도로 고려한다. 따라서 이때의 시간 복잡도는

$O(N^{2})$

가 된다. (계수는 제거한다.)

둘째로, 만약 시간 복잡도가 $O(N+M)$과 같이 N과 M 중 어떤 것이 더 큰지 알 수 없을 경우, 둘 다 표기한다.

셋째로, 불필요한 상수는 제거한다. 예를 들어,

1. $O(3n^{2})$ (X) -> $O(n^{2})$ (O)
2. $O(log_{3}n)$ (X) -> $O(logn)$ (O)

마지막으로, 필요한 연산의 수가 1회, 2회 등과 같이 상수일 경우, $O(1)$로 표기한다.

위 내용을 바탕으로, 아래 문제들을 풀어 보자.

1. 똑같은 문제를 푸는 데 시간 복잡도 $O(1),O(N),O(N^{2}),O(N^{3})$의 알고리즘이 있다. N이 매우 큰 경우, 빠른 알고리즘부터 차례로 나열해 보자.
2. n명의 학생이 있고, 키가 모두 서로 다르다. 이때 두 번째로 키가 큰 학생의 키를 구하는 가장 빠른 알고리즘의 시간 복잡도는 무엇일까? 단 $n\geq 2$이다.
3. n명의 학생이 있고, 키가 모두 서로 다르다. 여기서 세 명의 학생을 뽑아 키의 합을 최대로 만드려고 한다. 이 방법을 찾는 시간 복잡도는 무엇일까? 단 $n\geq 3$이며, 두 수를 더하는 데 걸리는 시간은 $O(1)$로 계산한다.
4. 두 자연수 a, b가 있다. a의 b제곱을 계산하는 데 걸리는 시간 복잡도는 얼마일까? 단, 두 수를 곱하는 데 걸리는 시간은 $O(1)$로 계산한다.
5. 길이가 n인 수열 $a_{1},a_{2},\cdots ,a_{n}$이 있다. 두 자연수 $i,j(1\leq i\leq j\leq n)$가 주어졌을 때, $a_{i}+a_{i+1}+\cdots +a_{j-1}+a_{j}$를 계산하라는 질문이 Q회 들어온다. Q번의 질문에서 각각의 $i,j$가 다를 수도 있다. 이때 Q번의 질문을 모두 처리하는 가장 빠른 알고리즘의 시간 복잡도는? 단, 두 수를 더하는 데 걸리는 시간은 $O(1)$로 계산한다.

1번 (해결)

1. 알고리즘의 시간 복잡도가 $O(1)$인 알고리즘이 제일 빠르고, 그 다음으로 빠른 것부터 $O(N),O(N^{2}),O(N^{3})$인 순으로 알고리즘이 빠릅니다. 왠지 수능 국어 비문학 느낌이 나는데요 — Malgok1 (토론·기여) 2019년 12월 19일 (목) 20:13 (KST)

   맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 20:14 (KST)

2번 (해결)

1. 어차피 최대값 찾은 뒤 같은 알고리즘을 돌리며 최대값과 현재값이 같은지만 판별하는 과정만 추가하면 됩니다. 고로 시간복잡도는 똑같이 O(N) 입니다. Sleep (토론) 2019년 12월 19일 (목) 21:09 (KST)

   정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 22:29 (KST)

3번 (해결)

1. 마찬가지로 제일 키가 큰사람, 두번째로 키가 큰사람, 세 번째로 키가 큰사람을 구해 더하면 됩니다. 마찬가지로 각각의 과정의 시간복잡도가 O(N) 입니다. 따라서 구하는 알고리즘의 시간복잡도 역시 O(N)이 됩니다. Sleep (토론) 2019년 12월 19일 (목) 21:10 (KST)

   정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 22:29 (KST)

4번 (해결)

1. 곱셈을 총 b-1번 해야 합니다. 따라서 O(b) Sleep (토론) 2019년 12월 19일 (목) 21:13 (KST)

   더 빠른 방법이 있습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 22:29 (KST)

   1. 2진수를 활용하면 O(ln b). 예를 들면 b^8 이면 b*b를 계산한 뒤 이걸 제곱하고 또 다시 이걸 제곱하는 느낌? Sleep (토론) 2019년 12월 19일 (목) 22:35 (KST)

      맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
      만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 23:35 (KST)

2. 곱셈을 총 b-1번 해야 하므로 O(b-1)입니다. — Malgok1 (토론·기여) 2019년 12월 19일 (목) 22:18 (KST)

   가장 큰 항만 신경써야 하므로 -1은 빼는게 맞습니다. Sleep (토론) 2019년 12월 19일 (목) 22:22 (KST)

5번 (해결)

1. 우선 수열 Sk = a1 + a2 +.... +ak를 계산합니다. 편의상 S0=0으로 정의하죠. S1~Sn까지의 값을 계산하는데 시간복잡도는 n입니다. Sk=Sk-1+ak라는 점화관계를 이용하면 되니까요. 이제 질문을 받습니다. i,j값을 입력받으면 S(j)-S(i-1)값을 출력하면 됩니다. 이 과정의 시간복잡도는 Q입니다. 따라서 답은 O(N+Q)입니다. Sleep (토론) 2019년 12월 19일 (목) 21:17 (KST)

   정답입니다. 사용하는 용어를 보니 예전에 알고리즘 공부를 하신 적이 있는 것 같네요. 혹시 올림피아드도 나가 보셨나요? -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 22:29 (KST)

시간복잡도는 대충 어디서 주워들은게 있고 알고리즘 공부를 제대로 해본 적도 없습니다. 다만 행정병으로 많이 굴렀을 뿐. Sleep (토론) 2019년 12월 19일 (목) 22:36 (KST)

1일차 정해

1번

$O(1)<O(N)<O(N^{2})<O(N^{3})$

2번

1. 최댓값을 찾는다. $O(N)$
2. 최댓값이 아닌 값들 중, 최댓값을 찾는다. $O(N)$
3. 2번 과정에서 구한 것이 최종 답이다.

시간 복잡도: $O(N)$

3번

키의 합을 최대로 만드려면 단순히 키가 가장 큰 세 명을 뽑으면 된다. 이 과정은 2번 문제의 과정을 그대로 응용하여 수행할 수 있다. 따라서 시간 복잡도는 $O(N)$.

4번

b=0일 때: $a^{b}=1$

b가 홀수일 때: $a^{b}=(a^{b-1})\times a$

b가 짝수일 때: $a^{b}=(a^{b/2})^{2}$

이제 시간 복잡도를 계산해 보자. b가 반절이 될 때마다 1~2번 정도의 계산이 이루어지므로, 시간 복잡도는 $O(log_{2}n)=O(logn)$이다.

5번

prefix sum 기법을 이용하면 된다. Sleep님의 답안이 정해와 같으므로 생략.

2일차 문제

지문

다항 시간 알고리즘이란, 시간 복잡도가 다항식인 알고리즘을 의미한다. 예를 들어, 시간 복잡도가 $O(n^{7})$ 또는 $O(n^{4}+nm)$인 알고리즘은 다항 시간 알고리즘인 반면, $O(3^{n})$나 $O(n!)$인 알고리즘은 다항 시간 알고리즘이 아니다.

결정 문제란 답이 Yes 또는 No로 정해지는 문제를 의미한다. P 문제와 NP 문제는 결정 문제의 부분집합이다.

P 문제는, 결정 문제들 중 다항 시간 이내에 풀 수 있는 문제를 의미한다. 어떤 문제를 풀 수 있는 가장 빠른 알고리즘의 시간 복잡도가 다항 시간 이내이면, 즉 $O(2^{n})$와 같은 지수 함수나 $O(n!)$와 같은 계승 함수가 아니라면, 이 문제는 P 문제이다.

반면 NP 문제의 정의는 매우 복잡하다. 이를 다른 방식으로 표현하자면, NP 문제는, 어떤 결정 문제의 답에 대한 단서가 주어진다면, 그 단서를 이용해 답을 다항 시간 이내에 입증(검산)할 수 있는 문제를 말한다.

P-NP 문제란, P 문제의 집합과 NP 문제의 집합이 같은지, 다른지를 알아내는 문제이다. 만약 NP 문제이면서 P 문제가 아닌 문제가 있다면, P≠NP이기 때문에 문제를 풀 수 있다. 하지만 불행하게도 아무도 이런 문제를 찾아내지 못했다. 이번 2일차 문제에서는 몇 가지 문제들을 살펴보고 왜 이것이 어려운지 확인해 보자. 6, 7번 문제는 P-NP 문제와 연관은 없지만, 1일차 문제의 연장선 상에 있다.

1. 모든 P 문제가 NP 문제라는 것을 간락하게 설명해 보자.
2. NP 문제가 아닌 문제는 P 문제가 아니라는 것을 증명해 보자.
3. P=NP임이 증명될 경우 암호계는 위기에 처하게 된다. 그 원인이 무엇일까?
4. n개의 수들로 이루어진 집합 S가 있다. S의 가능한 모든 부분집합에 대해, 부분집합의 원소의 합을 구한 뒤, 이 합들을 모두 더한 값을 구하고자 한다. 수학적으로는,
   $\sum _{T\subset S}\sum _{i\in T}i$
   을 구하는 것과 같다. 이 문제는 P 문제인가? 또 이 문제는 NP 문제인가?
5. 미지수와 식이 각각 n개인 일차연립방정식을 풀려고 한다. 이 문제가 NP 문제임을 보여라. 또, 이 문제가 P 문제임을 보여라.
   
   
6. N-Queen 문제는, N*N 정사각형 체스판에 N개의 퀸을 배치하는데, 서로 공격할 수 없게 하는 경우의 수를 구하는 문제이다. 이 문제는 P 문제이자, NP 문제이다. 이 문제를 풀 수 있는 다항 시간 알고리즘은 알려져 있으나, 찾기 매우 어렵다. 대신 시간복잡도가 $O(N!)$보다 빠른 알고리즘을 찾아 보자.
7. 변수가 x뿐인 N차 다항식 두 개가 있다. 이 다항식을 곱하는 $O(N^{2})$보다 빠른 알고리즘이 있을까?

p.s. 너무 잘 푸셔서 7번 문제를 추가했습니다.

1번 (해결)

1. 답을 구한 뒤 답과 입력이 일치하는지 비교하면 됩니다.117.111.25.162 2019년 12월 20일 (금) 20:12 (KST)

   맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 20일 (금) 20:26 (KST)

2번 (해결)

1. 명제 1의 대우입니다. Sleep (토론) 2019년 12월 20일 (금) 20:14 (KST)

   맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 20일 (금) 20:26 (KST)

3번 (해결)

1. 현 암호체계는 NP 문제를 활용해 뚫으려면 오래걸리지만 거꾸로 댄 암호가 설정한 값과 맞냐? 하는 것은 매우 쉬운 체계를 구축했습니다. P=NP라면, 저 "뚫으려면 오래걸리지만" 이라는 전제가 깨집니다.

자. 이렇게 써놓으니까 어렵습니다. 이제 쉬운 비유를 들죠.(비유는 세상을 바꾼 10가지 알고리즘의 공개키/비밀키 파트를 참고했습니다.)

군대에서 많이 쓰는 암구호를 생각해 봅시다.

답어를 받는 사람 입장에서는, 자신이 알고 있는 답어와 상대방이 댄 답어를 비교하면 됩니다.

암구호가 3자리고 한자 비교하는데 1초 걸린다고 하면 3초군요.(시간복잡도는 n)

그러나 암구호가 3자리라는 것만 아는 사람이 답어를 노가다로 뚫으려면? 한글 조합이 약 1만개 정도니

1만의 3승 하여 1조초 정도만 고생하면 되겠구군요. (시간복잡도는 10^4n)

이렇게 시간복잡도가 비-다항식인 특정 문제들은 시간 복잡도가 다항식으로 나타나는 문제에 비해 엄청나게 오래걸립니다.

근데 여기서, P=NP란 것이 밝혀진다? 그러면 우리가 기존에 "아 이거 시간복잡도가 다항식 꼴로 안나오고 엄청 오래걸려" 하던 문제들도

어떻게 노력만 하면 시간 복잡도가 다항식 꼴로 나오는 알고리즘을 찾아 엄청 빠른 시간내에 뚫어버릴 수 있다는 겁니다.

요컨데 위의 시간복잡도 10^4n의 brute-force알고리즘이 시간복잡도가 n^20인 알고리즘으로 교체되었다? 그래도 해결에 걸리는 시간은 0.000001배로 엄청나게 줄어버립니다.

Sleep (토론) 2019년 12월 24일 (화) 12:00 (KST)

맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 25일 (수) 10:52 (KST)

4번 (해결)

1. 2^n-1에 s원소의 합을 곱하면 됩니다. 따라서 p문제이며 1번 문제에 의해 np문제이기도 합니다.Sleep (토론) 2019년 12월 20일 (금) 20:40 (KST)

   맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 12월 20일 (금) 21:03 (KST)

5번 (해결)

1. gauss elemination 과정을 생각해보면 윗 줄의 정수배를 아랫줄에서 쭈르륵 빼주면서 길이순으로 정렬하는 과정을 거칩니다. 두 과정은 모두 행(줄)의 갯수에 대한 다항함수로 나타낼 수 있습니다.

K+1 번째 행에 대해 생각해보면

빼기 : o(k) 정렬하기 : o(k^2)

따라서 전체 과정은 o(n^4)정도의 시간복잡도가 걸립니다. 따라서 p문제이며 문제 1에 의해 np문제이기도 합니다. Sleep (토론) 2019년 12월 20일 (금) 20:39 (KST)

가우스 소거법을 아신다니... 대체 뭐하는 분이세요? -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 20일 (금) 21:06 (KST)

학부생입니다. 그나마 읽은 알고리즘책은 군대 후임 책 뺏어서 읽은게 전부입니다. 다만 비슷한 주제를 한번이라도 접해보았는가, 그렇지 않았는가에 따라 체감되는 난이도 차이가 너무 큽니다. 주제넘게 건의하면, 도시대항 토너먼트 수학대회류의 문제 혹은 수학동아 09년도쯤에 연재된 카이스트에서 내준 수학문제 시리즈 쪽으로 방향을 선회하시는것이 좋을 듯 싶습니다. 너무 진입장벽이 높아진것 같습니다.Sleep (토론) 2019년 12월 21일 (토) 12:42 (KST)

사실 진입장벽을 높인 이유가 Sleep님 때문인데, 이렇게 잘 푸시면 저로써는 뭐 할 말이 없네요. 4회차 3번 문제 증명을 써내는 수준을 보고 '알고리즘'이라는, 대부분의 사람들에게 생소할 수 있는 분야를 가지고 문제를 내기로 했는데, 이것마저도 접해보신 적 있다고 하면 전 대체 어떻게 할까요. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 21일 (토) 12:52 (KST)

6번 <명예의 전당 문항>

1. NP 완전이라면 Backtracking 같은 걸로 경우의 수를 쳐내면 되지 않을까요...

가령 구석부터 퀸을 놓고 다음 퀸을 놓을 자리를 옆 줄에서 찾으면서 자리가 없으면 돌아가서 이전 퀸을 옮긴다든지...

더 자세한 건 묻지 말아주세요. 알고리즘 수업 C 맞은 안습한 학부생입니다. --Senouis (토론) 2020년 1월 26일 (일) 23:36 (KST)

네, N-Queen 문제는 NP 완전 문제가 맞습니다. 하지만 백트래킹 풀이는 $O(N!)$의 시간 복잡도를 가지고 있습니다. 제가 찾아낸 바로는, 이보다 더 빠른 시간 내에 동작하는 알고리즘이 있습니다. 하지만 실질적인 효율성은 백트래킹보다 나쁩니다. 저는 이것을 통해서 시간 복잡도가 알고리즘의 효율성을 보여주는 것은 아니라고 말하고 싶었던 것입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 27일 (월) 10:44 (KST)

아아, 그럼 체스판에 관한 문제니까 그냥 체스말을 배치하는 일의 시간 복잡도가 다항식 시간 이라는 점을 이용해야겠네요.

1. 랜덤하게 체스판에 퀸을 놓는다. O(n)이지만 상관없다.
2. 매 줄에 있는 퀸마다 해당 줄의 가장 적게 공격받는 위치 또는 위치들을 찾아 해당 위치에 말을 옮긴다. 이때 시간복잡도는 n개의 말에 대해 각n개의 말의 공격위치를 n개의 칸에 대해 조사하므로 최대 O(n^2 * n) = O(n^3)이 된다.
3. 안되면 퀸을 재배치하고 이상의 과정을 반복한다. 이때 첫 줄의 퀸이 이전에 놓았던 위치와 같지 않게 배치된다. 최대 n번 반복하게 된다.

최종적으로 O(n^4)를 기대할 수 있겠습니다. 물론 해가 있는데도 해가 없다는 잘못된 결과를 출력할 수 있기에 몬테 카를로 알고리즘 같지만 이걸 제시해봅니다. --Senouis (토론) 2020년 1월 27일 (월) 13:52 (KST)

제가 낸 문제는, 가능한지를 따지는 것이 아닌, 몇 가지 방법으로 가능한지를 찾는 것입니다. 이 방법으로는 (당연하게도) 모든 경우의 수를 찾을 수 없습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 27일 (월) 16:12 (KST)

7번 <추가 문제 / 명예의 전당 문항> (해결)

1. 다음과 같은 분할 정복 알고리즘을 생각합시다.

T(N) : N차 식 2개를 곱할때 걸리는 시간복잡도

분류	n=2k-1	n=2k
계산법	(f1 + f2 x^n)(g1 + g2 x^n)	(f1 + f2 x^n)(g1 + g2 x^n)
f1	n-1차함수	n-1차함수
f2	n-1차함수	n차함수
g1	n-1차함수	n-1차함수
g2	n-1차함수	n차함수
전개식	f1g1 + x^n(f1g2+f2g1) + x^2n(g1g2)	f1g1 + x^n(f1g2+f2g1) + x^2n(g1g2)
f1g1	0~2(n-1)차	0~2(n-1)차
(f2g1+f1g2)x^n	n~3n-2	n~3n-1
f2g2x^2n	2n차 부터 끝까지	2n차 부터 끝까지
겹치는 차수에 대한 덧셈	O(N/2)*2	O(N/2)*2
f1g1,f2g2 연산에 걸린 시간	T(N/2)	T(N/2)
f2g1+f1g2 = (f1+g1)(f2+g2)-f1g1-f2g2 연산에 걸린 시간	T(N/2) + O(N)*2 + O(N/2)*2	T(N/2) + O(N)*2 + O(N/2)*2
총 연산시간	3T(N/2)+O(N/2)*8	3T(N/2)+O(N/2)*8

만약 T(N)이 N^2보다 같거나 더 빠른 증가추세를 보인다면 T(N) >= 4T(N/2) > 3T(N/2)+4O(N) =3T(N/2)+8*O(N/2)가 성립합니다. 이는 모순입니다.

따라서 이 분할정복 알고리즘은 O(N^2)보다 더 빠르게 작동합니다.

맞습니다. 추가로, Master Theorem을 이용해 이 알고리즘의 시간 복잡도를 계산할 수 있고, 이때 시간 복잡도는 $O(n^{log_{2}3})$입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 21일 (토) 12:59 (KST)

더 덧붙이자면, 제시해 주신 분할 정복 알고리즘은 카라추바(Karatsuba) 알고리즘으로, 큰 N자리 수의 곱셈을 빠르게 하기 위해 고안된 것입니다. Karatsuba 알고리즘보다 빠른 알고리즘으로는 FFT(Fast Fourier Transform) 등이 존재합니다. FFT의 경우 $O(nlogn)$의 시간 복잡도에 구할 수 있습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 21일 (토) 13:02 (KST)

잘못 설명된 부분이 있어서 고쳤습니다. Master theorm이 뭔지 간략하게 알 수 있을까요? Sleep (토론) 2019년 12월 21일 (토) 13:32 (KST)

재귀적으로 정의되는 함수의 시간 복잡도를 계산할 수 있는 공식입니다. 자세한 내용은 구글에 검색해 보시면 잘 나옵니다. 172.30.1.254 2019년 12월 21일 (토) 14:16 (KST)

• 돌아가기