我有一个算法,我需要帮助找到它的复杂性(最严格的上限)
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)
。你能帮我找到最紧的界限吗?