为while循环

什么是为while循环

x = 1 
while(x < SomeValue) 
{ 
    x *= 2; 
}

的时间复杂度时间复杂度，我相信这是O（N），作为循环将持续一个固定数量的迭代。我的假设是否正确？

来源

2016-08-10 Cdesai

我不介意错误，但只是如果我错了，那么什么是正确的答案。 – Cdesai

如果它是一个固定的迭代次数，它有多少？ –

时间复杂度为O（log（n）），因为x正在呈指数增长。

来源

2016-08-10 21:49:27 Brian

除非'SomeValue <= 1'，在这种情况下复杂度是O（1）。 – cybersam

@cybersam您可以将该参数应用于任何大O表示法。如果你指定'n'的值，你总是可以将它解决为一个常数，从而将它变成O（1）。 – Brian

如果SomeValue> 1，那么复杂度是'O（log（SomeValue））'，而不是'O（1）'。 – cybersam

循环将在O中执行（日志n）时间。希望数学能让理性更清楚。每次迭代都是恒定的。为了寻找与SomeValue迭代次数，我们称之为吨，你可以看到ñ^次迭代后，x将值2 ⁿ。该循环结束一次x≥t。因此，为了找到满足或超过t所需的迭代次数，针对x插入2≈并且解决t。您得到t = log 2（n）。因此，O（日志n）时间。

来源

2016-08-10 22:06:02 kamoroso94

回答

相关问题