尝试计算函数的时间和存储复杂度 (C)
Trying to calculate time and storage complexity for a function (C)
编辑:我想出了如何正确计算时间复杂度,但仍然无法计算出存储复杂度。
编辑:想通了一切。
我尝试解决一道复杂的问题,但失败了。
答案应该是:时间复杂度 - n(m+n),存储复杂度 - m+n。
请帮助我理解我哪里错了,并建议一种方法来更好地understand/solve这些类型的问题。
函数如下:
void f(int n, int m){
if (n <= 1) {
int *arr=malloc(m*sizeof(int));
for (int i=0; i<m; i++) arr[i] = 0;
free(arr);
return;
}
f(n-1, m+1);
f(n%2, m+1);
}
据我所知,"free(arr)" 释放了 malloc 分配的内存,这使得 malloc 在时间复杂度方面变得不那么重要了。
编辑:有人向我解释说,即使我们使用 'free' malloc 仍然被考虑在内(space cpmlexity wise)。
我看到第一个函数调用使函数调用自身 n 次,当发生这种情况时,m 增加了 1 - n 次,所以第一个 func 调用的时间复杂度是 n(m+1) 并且存储复杂度 n- 因为在递归中有 n 次调用函数。编辑:最终弄明白了。
第二个函数调用调用函数 log(n) 次,m 递增 log(n) 次,这使得此调用的时间复杂度为:log(n)(m+1)。
存储 complexity:log(n).
所以总时间复杂度为n(m+1),总存储复杂度为n。
这其实是一个棘手的问题!
第二个函数调用 f(n%2, m+1)
只是调用递归 f 一次,因为它计算了 n 到 2 的提醒,它可以是 1 或 0!在这两种情况下,都返回 f 函数而无需任何进一步的递归调用。
所以不是log n.
函数 f 在 f(n-1, m+1)
中被调用了 n 次,紧接着在 f(n%2, m+1)
中,它将再次被调用一次。如果只考虑n个因素就是O(2n)了。
现在考虑 m 因子,我们会注意到 if 中的循环重复 m 次,并且 m 在每次递归调用时递增 1(并且当它 returns 从递归调用返回时实际上递减!) 所以它将是 (m+n ... m+1) 的总和,即 O(mn+n(n+1)/2)。就是简化后的。
因此,考虑到这两个因素,时间复杂度 是 O(2n+mn+n(n+1)/2) 这实际上在简化后相当于 O(nm+n^2).
关于存储复杂度:第一次调用(m+1)m递增,会持续n次,第二次调用不会继续,所以存储复杂度 将是 O(n+m).
void f(int n, int m){
if (n <= 1) {
int *arr=malloc(m*sizeof(int));
for (int i=0; i<m; i++) arr[i] = 0;
free(arr);
return;
}
f(n-1, m+1);
f(n%2, m+1);
}
让我们重构它:
void f1(int m) {
int *arr = malloc(m*sizeof(int));
for (int i = 0; i < m; i++) {
arr[i] = 0;
}
free(arr);
}
void f(int n, int m){
if (n <= 1) {
f1(m);
return;
}
f(n-1, m+1);
f(n%2, m+1);
}
所以对于 f1 它很简单,- space 复杂度是 sizeof(int) * m
- 我们需要分配那么多 - 时间复杂度只是 m
- 我们正在遍历所有m
数组中的元素 arr
.
n%2
只能是1
或0
,所以我们可以用f(n%2, m+1);
代替f1(m+1)
。
void f(int n, int m){
if (n <= 1) {
f1(m); // (1)
return;
}
f(n-1, m+1); // (2)
f1(m + 1); // (3)
}
现在。如果 n > 1
那么我们调用 f(n-1, ...
直到 n <= 1
。对于每个 n > 1
,我们按相反的时间顺序调用 f1(m + 1)
(因为它在递归调用之后)。当我们到达 n <= 1
时, f1(m)
被调用 m = m(initial) + n(initial) - 1
次。
哦,也许是 n=5
的例子,然后:
- 初次调用
f(5, m)
所以 n=5
- n=5,所以我们调用
f(4, m+1)
// (2)
- n=4,所以我们调用
f(3, m+2)
// (2)
- n=3,所以我们调用
f(2, m+3)
// (2)
- n=2,所以我们调用
f(1, m+4)
// (2)
- n=1,所以我们调用
f1(m+4)
和 return // (1)
- n=2,在 (2) 之后,所以我们调用
f1(m+4)
// (3)
- n=3,在 (2) 之后,所以我们调用
f1(m+3)
// (3)
- n=4,在 (2) 之后,所以我们调用
f1(m+2)
// (3)
- n=5,在 (2) 之后,所以我们调用
f1(m+1)
// (3)
我们可以看到 f1(m+4)
被调用了两次,并且我们正在以相反的顺序调用 f1(m + i)
从 i=1
到 i=4
.
我们可以"unfold"函数:
void f(int n, int m){
f1(m + n - 1);
for (int i = n - 1; i > 0; --i) {
f1(m + i);
}
}
由于 m
和 n
都接近无穷大,因此 +1
或 -1
没有任何意义。
space复杂度是f1(max(m + i, m + n - 1))
的space复杂度,因为f1
每次都释放内存。所以它是 (m + n - 1) * sizeof(int)
即 (m + n) * sizeof(int)
,即 m + n
。
时间复杂度取决于我们调用f1
函数的次数。我们看到我们调用:
f1(m + n - 1)
f1(m + n - 1)
f1(m + n - 2)
...
f1(m + 2)
f1(m + 1)
所以时间复杂度为
(m + n - 1) + ((m + n - 1) + (m + n - 2) + ... + (m + 1))
(m + n - 1) + (n - 1) * m + ((n - 1) + (n - 2) + ... 1)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
// the `*2`, `/2`, `+1` and `-1` mean nothing close to infinity
m + n + n * m + n * n
m + n + m * n + n * n
m * (n + 1) + n * (n + 1)
(m + n) * (n + 1)
(m + n) * n
编辑:我想出了如何正确计算时间复杂度,但仍然无法计算出存储复杂度。
编辑:想通了一切。
我尝试解决一道复杂的问题,但失败了。
答案应该是:时间复杂度 - n(m+n),存储复杂度 - m+n。
请帮助我理解我哪里错了,并建议一种方法来更好地understand/solve这些类型的问题。
函数如下:
void f(int n, int m){
if (n <= 1) {
int *arr=malloc(m*sizeof(int));
for (int i=0; i<m; i++) arr[i] = 0;
free(arr);
return;
}
f(n-1, m+1);
f(n%2, m+1);
}
据我所知,"free(arr)" 释放了 malloc 分配的内存,这使得 malloc 在时间复杂度方面变得不那么重要了。 编辑:有人向我解释说,即使我们使用 'free' malloc 仍然被考虑在内(space cpmlexity wise)。
我看到第一个函数调用使函数调用自身 n 次,当发生这种情况时,m 增加了 1 - n 次,所以第一个 func 调用的时间复杂度是 n(m+1) 并且存储复杂度 n- 因为在递归中有 n 次调用函数。编辑:最终弄明白了。
第二个函数调用调用函数 log(n) 次,m 递增 log(n) 次,这使得此调用的时间复杂度为:log(n)(m+1)。 存储 complexity:log(n).
所以总时间复杂度为n(m+1),总存储复杂度为n。
这其实是一个棘手的问题!
第二个函数调用 f(n%2, m+1)
只是调用递归 f 一次,因为它计算了 n 到 2 的提醒,它可以是 1 或 0!在这两种情况下,都返回 f 函数而无需任何进一步的递归调用。
所以不是log n.
函数 f 在 f(n-1, m+1)
中被调用了 n 次,紧接着在 f(n%2, m+1)
中,它将再次被调用一次。如果只考虑n个因素就是O(2n)了。
现在考虑 m 因子,我们会注意到 if 中的循环重复 m 次,并且 m 在每次递归调用时递增 1(并且当它 returns 从递归调用返回时实际上递减!) 所以它将是 (m+n ... m+1) 的总和,即 O(mn+n(n+1)/2)。就是简化后的。
因此,考虑到这两个因素,时间复杂度 是 O(2n+mn+n(n+1)/2) 这实际上在简化后相当于 O(nm+n^2).
关于存储复杂度:第一次调用(m+1)m递增,会持续n次,第二次调用不会继续,所以存储复杂度 将是 O(n+m).
void f(int n, int m){
if (n <= 1) {
int *arr=malloc(m*sizeof(int));
for (int i=0; i<m; i++) arr[i] = 0;
free(arr);
return;
}
f(n-1, m+1);
f(n%2, m+1);
}
让我们重构它:
void f1(int m) {
int *arr = malloc(m*sizeof(int));
for (int i = 0; i < m; i++) {
arr[i] = 0;
}
free(arr);
}
void f(int n, int m){
if (n <= 1) {
f1(m);
return;
}
f(n-1, m+1);
f(n%2, m+1);
}
所以对于 f1 它很简单,- space 复杂度是 sizeof(int) * m
- 我们需要分配那么多 - 时间复杂度只是 m
- 我们正在遍历所有m
数组中的元素 arr
.
n%2
只能是1
或0
,所以我们可以用f(n%2, m+1);
代替f1(m+1)
。
void f(int n, int m){
if (n <= 1) {
f1(m); // (1)
return;
}
f(n-1, m+1); // (2)
f1(m + 1); // (3)
}
现在。如果 n > 1
那么我们调用 f(n-1, ...
直到 n <= 1
。对于每个 n > 1
,我们按相反的时间顺序调用 f1(m + 1)
(因为它在递归调用之后)。当我们到达 n <= 1
时, f1(m)
被调用 m = m(initial) + n(initial) - 1
次。
哦,也许是 n=5
的例子,然后:
- 初次调用
f(5, m)
所以 n=5 - n=5,所以我们调用
f(4, m+1)
// (2) - n=4,所以我们调用
f(3, m+2)
// (2) - n=3,所以我们调用
f(2, m+3)
// (2) - n=2,所以我们调用
f(1, m+4)
// (2) - n=1,所以我们调用
f1(m+4)
和 return // (1) - n=2,在 (2) 之后,所以我们调用
f1(m+4)
// (3) - n=3,在 (2) 之后,所以我们调用
f1(m+3)
// (3) - n=4,在 (2) 之后,所以我们调用
f1(m+2)
// (3) - n=5,在 (2) 之后,所以我们调用
f1(m+1)
// (3)
我们可以看到 f1(m+4)
被调用了两次,并且我们正在以相反的顺序调用 f1(m + i)
从 i=1
到 i=4
.
我们可以"unfold"函数:
void f(int n, int m){
f1(m + n - 1);
for (int i = n - 1; i > 0; --i) {
f1(m + i);
}
}
由于 m
和 n
都接近无穷大,因此 +1
或 -1
没有任何意义。
space复杂度是f1(max(m + i, m + n - 1))
的space复杂度,因为f1
每次都释放内存。所以它是 (m + n - 1) * sizeof(int)
即 (m + n) * sizeof(int)
,即 m + n
。
时间复杂度取决于我们调用f1
函数的次数。我们看到我们调用:
f1(m + n - 1)
f1(m + n - 1)
f1(m + n - 2)
...
f1(m + 2)
f1(m + 1)
所以时间复杂度为
(m + n - 1) + ((m + n - 1) + (m + n - 2) + ... + (m + 1))
(m + n - 1) + (n - 1) * m + ((n - 1) + (n - 2) + ... 1)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
// the `*2`, `/2`, `+1` and `-1` mean nothing close to infinity
m + n + n * m + n * n
m + n + m * n + n * n
m * (n + 1) + n * (n + 1)
(m + n) * (n + 1)
(m + n) * n