简单算法复杂度

Question

我有一个算法，我需要帮助找到它的复杂性(最严密的上界)

for(int i = 0; i < n/2; i++)
    for(int j = 0; j < n/4; j++)
        for(int k = 0; k < n; k++)
            x++;

我的分析是，如果n不被划分在每个for循环中，那么它就是O(n^3)。这种复杂性仍然成立，因为每个"for循环“都会将每个操作降低到O(log n)复杂度，因为它每次执行循环时都会划分n个，使其越来越小(至少比O(n)小)。

我想说的是，答案是O(log n)和O(n^3)之间。你能帮我把最紧的绑起来吗？

Answer 1

从内环开始：

for(int k = 0; k < n; k++)
    x++;

显然是O(n)。

在此之上的一层是：

for(int j = 0; j < n/4; j++)

是O(n)，因为j需要n/4才能到达n，我们知道O(n/4) = O(n)

就像这样，外循环是O(n).so，复杂度是O(n^3) ，因为有三个嵌套循环，每个循环都有O(n)，它们之间没有相互影响。

Answer 2

假设每一步都需要时间C.对于k-循环，所花费的时间是Cn.对于j-循环，完成迭代所需时间为(C_n)_n/4=C(n^2)/4 (i-循环)，完成迭代所需时间为(C*(n^2)/4)n/2=C(n^3)/8。

所以总时间taken=(C/8)*(n^3)

由于C/8是一个常数，所以在考虑大-O表示法时可以忽略它。因此，时间Complexity=O(n^3)。

Answer 3

for(int i = 0; i < n/2; i++)    --> n/2
    for(int j = 0; j < n/4; j++)  --> n/4
        for(int k = 0; k < n; k++)  --> n
            x++;

因此，总复杂度是O((n^3)/8)，即O(n^3)。