행렬 A의 2 * 2의 제곱은 단지 5 배의 곱이 필요하다는 것을 보여줌으로써 O (n^log5)임을 알 수 있습니다. 지금까지는 아무런 문제가 없었지만 이후에 왜 다른 제곱 경우 (다른 n * n 크기)로 일반화 할 수 없는지 2 가지 이유를 설명하고자 할 때 다음과 같이 하나만 만들 수 있습니다.행렬의 제곱과 실행 시간
첫 번째 그 이유는 내가 예를 들어 3 * 3 행렬을 곱해서 최소한 6 배의 곱셈을한다고 결론 내렸다. 따라서 실행 시간은 적어도 O (n^log6)이고, n^epsalon은 O (n^log5) 따라서 모든 경우에 대해 O (n^log5)를 일반화 할 수는 없습니다. 이제 다른 이유가 필요하지만 두 번째 이유를 설명하는 방법을 알아낼 수 없습니다 (아이디어를 제시하기위한 힌트가 필요합니다).
예제에서 실행 시간을 big-o 표기법으로 파생시킬 수 없습니다. Big-O 표기법은 인수의 증가 (이 경우 행렬 크기 n)에 따라 알고리즘의 복잡성이 어떻게 조정되는지에 대해 알려주므로 실제로 대략적으로 실험하고 싶다면 적어도 여러 테스트 크기의 실행 시간을 계산해야합니다 .
하지만 100x100 행렬을 손으로 정사각형으로 표시하는 최적의 방법을 찾을 수 있을지는 모르지만 실제로는 어려운 문제입니다. 우리가 확실히 알고있는 것은 매트릭스 매트릭스 제품보다 더 복잡하지 않다는 것입니다. 우리는 적어도 한 번 이상 행렬의 모든 항목을 살펴야하기 때문에 오메가 (n^2)의 하한값이 있습니다. 그리고 그 복잡성으로 알려진 알고리즘이 있기 때문에 대략 O (n^2.3729)의 (이론적 인) 완벽한 알고리즘에 대한 상한선이 있습니다.
을 (http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication 참조) 덧붙여 2.3729 당신이 최소 제안 < LOG6 - 다시 한 번 때문에, 3 × 3 행렬 6 곱셈을해야 할 수도 있다는 말씀을 모순되지 않습니다 : O-표기는 점근 적 행동에 대한 관심 n이 커질수록 실행 시간이 짧아지며, 개인 n의 특정 실행 시간은 아닙니다.
고정 된 크기의 행렬을 Squaring하는 것은 고정 된 수의 곱셈 만 필요하기 때문에 시간 O (1)을 취합니다. 런타임이 O (n^log 5)라고 말하면 기술적으로는 올바르지 만 결론을 내리는 것은 잘못된 것입니다. – templatetypedef
고마워요, strassen 분해에 의해 모든 행렬 곱셈은 T (n) = 7T (n/2) + n^2이고 또한 2 * 2 행렬을 제곱함으로써 알고 있습니다. O (n^log5) 다른 경우는 T (n)> = 6T (n/2) + n^2이므로 O (n^log5)를 일반화 할 수 없음을 나타냅니다. 이제 좀 더 설명해 주시겠습니까? –
"2x2 행렬을 제곱 한 것은 O (n^log 5)임을 알고 있습니까?" 로그 5는 어디에서 왔습니까? – templatetypedef