형들 궁금한거....

[익명(112.164)]

내가 왕초보라 그러는데...
x*y 는 x를 y번 더한거로 알아서 인식하지 않아?
그런데 둘다 변수일때  x*y는 O(1)인 이유가 궁금함...ㅜㅜ

[@(1.239)]

x를 y번 더하는게 아니기 때문이지

[@(1.239)]

곱셈 알고리즘이 따로있음

[익명(112.164)]

어떻게?????

[7냥이집사(211.179)]

연산 극혐

[@(1.239)]

뭐였드라 무슨 농부의 방법이었나 하는 알고리즘이 있었는데

[@(1.239)]

암튼 곱셈은 O(1)이 맞음

[익명(112.164)]

진짜? 크기에따라 달라지는게 아니야????

[@(1.239)]

아 미안하다 엄밀히 말하면 O(n^1.53)이었나 그럼. 정수곱셈에 한해서.

[@(1.239)]

카라추바 알고리즘 검색하면 나올걸

[익명(112.164)]

그럼 mit강의가 틀린거?ㅜㅜ

[@(1.239)]

근데 작업비용계산할때 그런걸 따지지는 않음.

[@(1.239)]

반복프로세스나 재귀프로세스가 얼마나 돌아가냐 이런거에 따른거지 뭐...