Divde & Conquer할 때 배우는 큰 수 곱셈 문제인데
저거 n자릿수를 가지는 두 정수 u와 v를 곱하면 시간복잡도가
W(n) = 4W(n/2) + cn이 나온다는데
앞에 4W(n/2)는 곱셈하는데 걸리는 시간
뒷부분 cn이 덧셈하는데 걸리는 시간이거든
곱셈 시간복잡도는 이해했어.
근데 왜 덧셈 시간이 cn인것이야? c는 상수니까 제쳐두고 왜 n밖에 안걸려?
uv에서만 봐도 덧셈이 3개 있고, 그 하위 단계로 내려가는 녀석이 4놈이나 되어서
n/2에서는 3 * 4 = 12개씩 있는거 아냐?
그 밑에는 또 더 많아질거고..
근데 왜 그냥 n으로 나타내면 되는거야? 내가 잘못생각하는건가??
님이 생각하는건 작은문제에 포함시켜야지
저 식을 2번 적용해보셈
uv를 2번 적용하면, 덧셈의 수가 상수배 이상 늘어나는거 같은데..
더발생하는건 맞음 하나의 문제에서는 cn만큼 발생하는데 문제 자체가 늘었으니
uv에 현재 덧셈 갯수가 3개인데, uv 안에 xw, xz, wy, yz가 있잖아. 여기에 각각 또 3개씩 들어가 있을거고.. 그 하위로 나눠지는 곱셈 안에 덧셈이 3개씩 들어가 있는거 아냐?? 그럼 덧셈도 W(n/2)에 관한 식으로 나타나는거 아니냔 말인데 정답은 cn이 맞거든. 근데 왜 cn인지 이해를 못하겠어
저 식은 복잡도를 바로 표현하는게 아니라 분할된 문제와 분할되기 전 문제사이의 관계식
cn은 전체 덧셈의 복잡도가 아니라 한번의 분할정복 과정에서 발생하는 덧셈의 복잡도
키야~ 수학 공식보고 저렇데 답변하는 새끼들은 참으로 부럽다
그럼 앞의 곱셈의 수는 왜 W(n/2)로 표현한거야 ㅠㅠ?
작은 문제로 분할하기때문에 님이 걱정하는것 처럼분할된 문제에서 또 덧셈이 발생함 W(n/2)는 곱셈이 아니라 분할된 문제의 복잡도를 의미함
W(n)의 의미가 n 자릿수를 가지는 u와 v를 곱했을 때 소요되는 곱셈의 수라고 했어.. 뒤의 cn은 u와 v를 곱했을 때 소용되는 덧셈의 수고.. 그래서 W(n)의 하위 분할은 W(n/2)가 되고 이것의 의미는 n/2 자릿수를 가지는 u와 v를 곱했을 때 소요되는 시간복잡도가 되야할 거 같은데.. (두 정수 u와 v의 곱셈에는 곱셈과 덧셈이 섞여 있으니까 이 둘을 합한 것으로 나타나야 하고, 그게 저 W(n)임)
머임 잘알고있네
님 말도 이해간다.. 그렇게만 이해하면 될려나??
근데 이거 배우기 전에 Strassen's Matrix Multilication 배웠었는데.. 거기선 덧셈의 수를 구했었거든. 왜냐면 행렬곱을 하는 과정에서 덧셈을 끼워지는 상황 때문에.. 그리고 마지막 T(n)에서 발생하는 덧셈의 수를 그 이전(바로 직전 분할)까지 발생한 덧셈의 수에 단순히 합해줬는데 이건 그건게 없어서 왜 그런가 싶어..
이 문제는 곱셈 자체를 직접 정의하는 상황이고 그 방법으로 분할정복을 쓰니까 분할과정에서 복잡도가 발생하고(cn) 분할된 문제는 더 작은 n에대해 문제를 푸는거
슈트라센 곱셈도 문제를작게 쪼개고(2x2행렬처럼 간주) 쪼개는 과정에 발생하는 덧셈만큼 복잡도 발생
본질적으로 같은거니까 공통점을 찾아보셈