编写程序实现: 1、输于两个n×n的矩阵A和B,实现乘积运算,并输出运算结果和计算时间; 2、逐渐增大矩阵A和B的规模,分析运算时间的变化。 3、用分治法的实现矩阵乘积运算,比较使用分治法前后的计算量差异。
时间: 2024-05-16 08:15:12 浏览: 13
以下是Python实现,首先我们来看一下普通的矩阵乘积运算:
```python
import time
def matrix_multiplication(A, B):
n = len(A)
C = [[0 for j in range(n)] for i in range(n)]
start = time.time()
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
end = time.time()
return C, end-start
```
接下来我们逐渐增大矩阵A和B的规模,分析运算时间的变化:
```python
import random
sizes = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
for size in sizes:
A = [[random.randint(0, 100) for j in range(size)] for i in range(size)]
B = [[random.randint(0, 100) for j in range(size)] for i in range(size)]
C, time_taken = matrix_multiplication(A, B)
print("Matrix multiplication with size", size, "took", time_taken, "seconds.")
```
我们再用分治法实现矩阵乘积运算:
```python
def divide_and_conquer_matrix_multiplication(A, B):
n = len(A)
if n == 1:
return [[A[0][0] * B[0][0]]], 0
else:
A11 = [[A[i][j] for j in range(n//2)] for i in range(n//2)]
A12 = [[A[i][j] for j in range(n//2, n)] for i in range(n//2)]
A21 = [[A[i][j] for j in range(n//2)] for i in range(n//2, n)]
A22 = [[A[i][j] for j in range(n//2, n)] for i in range(n//2, n)]
B11 = [[B[i][j] for j in range(n//2)] for i in range(n//2)]
B12 = [[B[i][j] for j in range(n//2, n)] for i in range(n//2)]
B21 = [[B[i][j] for j in range(n//2)] for i in range(n//2, n)]
B22 = [[B[i][j] for j in range(n//2, n)] for i in range(n//2, n)]
P1, _ = divide_and_conquer_matrix_multiplication(A11, [[B11[i][j]+B22[i][j] for j in range(n//2)] for i in range(n//2)])
P2, _ = divide_and_conquer_matrix_multiplication([[A11[i][j]+A12[i][j] for j in range(n//2)] for i in range(n//2)], B22)
P3, _ = divide_and_conquer_matrix_multiplication([[A21[i][j]+A22[i][j] for j in range(n//2)] for i in range(n//2)], B11)
P4, _ = divide_and_conquer_matrix_multiplication(A22, [[B21[i][j]-B11[i][j] for j in range(n//2)] for i in range(n//2)])
P5, _ = divide_and_conquer_matrix_multiplication([[A11[i][j]+A22[i][j] for j in range(n//2)] for i in range(n//2)], [[B11[i][j]+B22[i][j] for j in range(n//2)] for i in range(n//2)])
P6, _ = divide_and_conquer_matrix_multiplication([[A12[i][j]-A22[i][j] for j in range(n//2)] for i in range(n//2)], [[B21[i][j]+B22[i][j] for j in range(n//2)] for i in range(n//2)])
P7, _ = divide_and_conquer_matrix_multiplication([[A11[i][j]-A21[i][j] for j in range(n//2)] for i in range(n//2)], [[B11[i][j]+B12[i][j] for j in range(n//2)] for i in range(n//2)])
C11 = [[P5[i][j]+P4[i][j]-P2[i][j]+P6[i][j] for j in range(n//2)] for i in range(n//2)]
C12 = [[P1[i][j]+P2[i][j] for j in range(n//2)] for i in range(n//2)]
C21 = [[P3[i][j]+P4[i][j] for j in range(n//2)] for i in range(n//2)]
C22 = [[P5[i][j]+P1[i][j]-P3[i][j]-P7[i][j] for j in range(n//2)] for i in range(n//2)]
C = [[0 for j in range(n)] for i in range(n)]
for i in range(n//2):
for j in range(n//2):
C[i][j] = C11[i][j]
C[i][j+n//2] = C12[i][j]
C[i+n//2][j] = C21[i][j]
C[i+n//2][j+n//2] = C22[i][j]
return C, 0
```
最后我们比较使用分治法前后的计算量差异:
```python
sizes = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
for size in sizes:
A = [[random.randint(0, 100) for j in range(size)] for i in range(size)]
B = [[random.randint(0, 100) for j in range(size)] for i in range(size)]
C1, time_taken1 = matrix_multiplication(A, B)
C2, time_taken2 = divide_and_conquer_matrix_multiplication(A, B)
print("Matrix multiplication with size", size, "took", time_taken1, "seconds with normal algorithm.")
print("Matrix multiplication with size", size, "took", time_taken2, "seconds with divide and conquer algorithm.")
print("The two algorithms produced the same result:", C1 == C2)
```
由于分治法的计算量更小,因此我们可以看到随着矩阵大小的增加,分治法所需的时间增长速度更慢。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)