c - 函数的时间复杂度和空间

<分区>

我正在努力寻找下一个函数的复杂性

void what(int n) {
    int i;
    for (i = 1; i <= n; i++) {
        int x = n;
        while (x > 0)
            x -= i;
    }
}

我试图通过接下来的事情来解决它在查看空间时，我发现它只有 O(1)，因为没有使用它。想时间的时候我认为因为它每次被划分它将是 n(1+1/2 +1/4+....)=O(N.log(N)) 这是对的吗？谢谢

最佳答案

简单的分析给出了 O(N.log(N)) 的时间复杂度，但应该注意的是循环不计算任何东西:局部变量 x 递减 n/i 次并被丢弃。一个好的编译器应该能够将整个函数编译为空操作:void what(int n) {}，这导致了 O(1) 的复杂性，空间和时间。

关于c - 函数的时间复杂度和空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38940785/

相关文章：

c - 函数之间的文件指针上的 SegmentFault