三种整数乘法实现

用C语言分别对naive_mul、rec_mul和simple_mul (课堂上讲过的三种整数乘法)进行编程实现

没听到课，先写一遍python理解一下原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def is_even(t):
    if (t % 2 == 0):
        return True
    if (t % 2 == 1):
        return False

def naive_mul(a,b):
    if b == 0:
        return 0
    return a + naive_mul(a,b-1)

def rec_mul(a,b):
    c = a * (b // 2)
    if(b%2 == 0):
        return 2 * c
    if(b%2 == 1):
        return a + 2 * c

def simple_mul(a,b):
    if b == 0:
        return 0
    if is_even(b):
        return 2 * simple_mul(a,b//2)
    else:
        return 2 * simple_mul(a,b//2) + a

a = 3
b = 41
res_n = naive_mul(a,b)
res_r = rec_mul(a,b)
res_s = simple_mul(a,b)
print("nai: ")
print(res_n)

print("rec: ")
print(res_r)

print("rec: ")
print(res_s)

下面是c语言实现

naive_mul：

1
2
3
4
5
6
7
8
9
10
int naive_mul(int a, int b) {
    if (b == 0) {
        // 基本情况：当b为0时，返回0  
        return 0;
    }
    else {
        // 递归步骤：返回a加上a乘以(b-1)的结果 
        return a + naive_mul(a, b - 1);
    }
}

rec_mul:

1
2
3
4
5
6
7
8
9
10
11
int rec_mul(int a, int b) {
    int c = a * (b / 2); // 注意：这里直接使用乘法，没有递归  
    if (b % 2 == 0) {
        // 如果b是偶数，返回两倍的c  
        return 2 * c;
    }
    else {
        // 如果b是奇数，返回a加上两倍的c  
        return a + 2 * c;
    }
}

simple_mul:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int is_even(int n) {
    return n % 2 == 0;
}

// 递归乘法函数  
int simple_mul(int a, int b) {
    if (b == 0) {
        return 0;
    }
    if (is_even(b)) {
        return 2 * simple_mul(a, b / 2); // 注意：在C中，/ 对整数执行整数除法  
    }
    else {
        return 2 * simple_mul(a, b / 2) + a;
    }
}

测试对比这三种函数的效率:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>  
#include <time.h>  
  
int naive_mul(int a, int b) {  
    if (b == 0) {  
        return 0;  
    } else {  
        return a + naive_mul(a, b - 1);  
    }  
}  
  
int rec_mul(int a, int b) {  
    int c = a * (b / 2);  
    if (b % 2 == 0) {  
        return 2 * c;  
    } else {  
        return a + 2 * c;  
    }  
}  
  
int is_even(int n) {  
    return n % 2 == 0;  
}  
  
int simple_mul(int a, int b) {  
    if (b == 0) {  
        return 0;  
    }  
    if (is_even(b)) {  
        return 2 * simple_mul(a, b / 2);  
    } else {  
        return 2 * simple_mul(a, b / 2) + a;  
    }  
}  
  
void test_multiplication(int a, int b) {  
    clock_t start, end;  
    double cpu_time_used;  
  
    // Test naive_mul  
    start = clock();  
    int result_naive = naive_mul(a, b);  
    end = clock();  
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;  
    printf("naive_mul(%d, %d) = %d, time: %f seconds\n", a, b, result_naive, cpu_time_used);  
  
    // Test rec_mul  
    start = clock();  
    int result_rec = rec_mul(a, b);  
    end = clock();  
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;  
    printf("rec_mul(%d, %d) = %d, time: %f seconds\n", a, b, result_rec, cpu_time_used);  
  
    // Test simple_mul  
    start = clock();  
    int result_simple = simple_mul(a, b);  
    end = clock();  
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;  
    printf("simple_mul(%d, %d) = %d, time: %f seconds\n", a, b, result_simple, cpu_time_used);  
}  
  
int main() {  
    int a = 12345;  
    int b = 67890;  
  
    test_multiplication(a, b);  
  
    return 0;  
}

课后习题第12题

分析以下两种数列求积算法，分别给出它们的渐进复杂度，然后说明并编程验证它们之间有不同的计算效率

1
2
3
4
5
6
7
8
9
10
11
12
def product1(X):
    res = 1
    for i in range(len(X)):
        res *= X[i]
    return res

def product2(X):
    if len(X) == 0: return 1
    if len(X) == 1: return X[0]
    if len(X) == 2: return X[0] * X[1]
    l = len(X)
    return product2(X[0:(l + 1) // 2]) * product2(X[(l + 1) // 2:l])

首先分析这两种数列求积算法的渐进复杂度。

算法 product1 分析

product1 是一个简单的迭代算法，它遍历整个数组 X，并依次将每个元素乘到结果变量 res 中。因此，它的时间复杂度是 O(n)，其中 n 是数组 X 的长度。

算法 product2 分析

product2 是一个递归算法，它将数组 X 分成两半，然后分别递归计算每一半的乘积，最后将两个结果相乘。这是一个典型的分治算法，其时间复杂度可以通过递归关系式来表示：

$T(n) = 2T(\frac{n}{2}) + O(1)$

通过主定理我们可以得出这个递归关系式的时间复杂度是 O(n)，其中 n 是数组 X 的长度。尽管与 product1 具有相同的渐进复杂度，但递归算法通常由于函数调用栈的开销，实际运行时间可能会更长。

计算效率比较

虽然两个算法在渐进复杂度上是相同的，但在实际运行中，由于递归算法涉及到函数调用栈的开销，product2 可能会比 product1 慢

编程验证

下面是一个Python 脚本，用于比较两个算法的运行时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import time
import random

def product1(X):
    res = 1
    for i in range(len(X)):
        res *= X[i]
    return res

def product2(X):
    if len(X) == 0:
        return 1
    if len(X) == 1:
        return X[0]
    if len(X) == 2:
        return X[0] * X[1]
    l = len(X)
    return product2(X[0:(l + 1) // 2]) * product2(X[(l + 1) // 2:l])

# 生成一个随机数组
n = 10000000  # 数组长度
X = [random.random() for _ in range(n)]

# 测量 product1 的运行时间
start_time = time.time()
product1_result = product1(X)
end_time = time.time()
product1_duration = end_time - start_time

# 测量 product2 的运行时间
start_time = time.time()
product2_result = product2(X)
end_time = time.time()
product2_duration = end_time - start_time

# 输出结果
print(f"product1 result: {product1_result}, duration: {product1_duration}")
print(f"product2 result: {product2_result}, duration: {product2_duration}")
print(f"product1 is faster by {product2_duration - product1_duration} seconds")

运行结果

运行上述脚本， product1 的运行时间通常比 product2 要短，这是因为 product1 是一个简单的迭代算法，没有函数调用栈的开销，而 product2 是一个递归算法，涉及到多次函数调用。

结论

尽管两个算法在渐进复杂度上都是 O(n)，但由于递归算法的函数调用栈开销，product2 在实际运行中的效率通常低于 product1。