计算嵌套循环的时间复杂度

我在练习算法的时间复杂度，并且遇到了让我困惑的下面的代码。通常，我可以通过查看循环的数量来说明算法的复杂性，但下面的代码会使该假设衰减，因为有两个循环，我通常会假设复杂度为O（N^2），但是在第二个循环N平方。这使我得出复杂度为O（N）* O（N^2）= O（N^3）的结论。我在这里做错了什么？计算嵌套循环的时间复杂度

for (int i = 0; i*i < N; i++) 
    for (int j = 0; j*j < N*N; j++)

来源

2015-04-26 PRCube

外环将运行，而I^2 < N，或者等效地当我< SQRT（N）。这意味着外部循环将运行sqrt（N）次。

内循环将运行，同时j^2 < N^2，或同等运行j。这意味着内循环将运行N次（对于外循环的每次迭代）。因此，总迭代次数为（N^0.5）* N = N ^（3/2）。

来源

2015-04-26 23:11:44

也被称为O（n sqrt n） –

我认为这是相反的方式。外环为O（N），内环为O（N^2）。你能否证明你的答案是正确的，我想理解它。 – PRCube

@sasha你能解释为什么内部循环会在O（sqrt（N））中运行吗？ –

这具有时间复杂度O（n sqrt（n）） = O（n ^（3/2））。

外环需要O（sqrt（n））时间。它在经过〜sqrt（n）迭代后完成，因为我的平方增长，而N只是线性增长。

例如，考虑N = 100; i^2取值1，4，9，16，...，100，这是sqrt（N）不同的值。所以这是O（sqrt（n））。

内环需要O（n）的时间 - 同时服用j和N的平方根在每个步骤应清楚，这是一个线性循环。

例如，考虑N = 10; j^2取值为1，4，9，16，...，100，这是N个不同的值。所以这是O（n）。

来源

2015-04-26 23:13:46

计算嵌套循环的时间复杂度

回答

相关问题