java - 算法的原语运算

Question

我正在对算法进行分析，并停留在for and while loop上

假设我们有一个 for 循环

for (int i=0; i<n; i++)  

所以分配i = 0 = 1

i < n = n+1 (它将运行 n 次，最后一次检查哪个循环为 false 将是 n+1)

这就是困惑

i++ --> i++ 也会运行 n 次，但它正在执行两项不同的工作:增量和赋值。是 2n 还是只是 n？

在 while 循环中也是如此

while (i<n):会是2n吗？

我正在为 Big O 工作。

谢谢

Answer 1

通常，一项赋值相当于一项操作或“步骤”。这是因为通常使用 big-O notation 来测量算法的渐近运行时间。其中常数并不重要。

我通常将 i++ 算作一次操作。因此，为了回答您的问题，假设所有这些循环所做的都是递增 i，则运行时间将为 O(n)。但是，即使将其算作 2，运行时间仍然是 O(n)。