找不到这个C代码的时间复杂度？

-2

我很难找出如何计算一些代码的时间复杂度。我知道大O的基本知识，尽管我不能完全理解如何计算。找不到这个C代码的时间复杂度？

这是一个我无法解决的例子。希望你能：

void f(int n) { 
    int j, s; 
    for (j = 0, s = 1; s < n; j++, s*=2) 
     printf(“!”); 
    double values[j]; 
    for (int k = 0; k < j; k++) 
     values[k] = 0; 
    while (j--) 
     for (int k = 1; k < j; k++) 
      values[k] += 1.0/k; 
}

什么是运行时间？我很喜欢解释:)

来源

2016-02-13 sadasas sadsadas

什么是运行时或大O复杂度？ – juanchopanza

@juanchopanza哦，不知道这是两回事。像O（logn）或O（n^2）这样的计算，如果它对你来说意味着什么。对困惑感到抱歉。 –

一个好的开始可能是格式化代码，使其更具可读性。在C中，空白并不重要（字符串和字符文字之外），所以缩进对于编译器*来说并不重要。尽管如此，它对人类非常重要。 –

第一个循环迭代log2(n)次，计算j，最高位的顺序为n。复杂性O(log(n))。

第二个循环初始化一个大小为j的数组：时间和空间复杂度为O(log(n))。

第三回路是嵌套循环与嵌套循环迭代j到1次，总共j * (j - 1)/2次迭代j倍。这个时间复杂度为O(log(n)^2)，并且支配了之前的阶段。

该功能的整体时间复杂度为O(log(n)^2)，空间复杂度为O(log(n))。

来源

2016-02-13 12:18:12 chqrlie

终于有人用了。非常感激。谢谢。 –

找不到这个C代码的时间复杂度？

回答

相关问题