大 O 复杂度 java
Big-O complexity java
我是 Java 的新手，我的问题是大 O 复杂性。
对于a)来说，显然是O(n^2)对于嵌套循环
for ( int i = 0; i < n; i++)
for ( int j=0; j < n; j++ )
然而，对于 b)，在末尾有 sum++ 操作，并且嵌套循环中的复杂性，是否完全改变了它的 Big-O 复杂性？
int sum = 0;
for ( int i = 1; i <= n; i++)
for ( int j = n; j > 0; j /= 2)
sum++;
在您的第二个示例中，第一个 for 迭代 n 次，第二个迭代 log2(n) 次，因为您将 j 除以 2在每次迭代中。因此，复杂度为 O(n log2 n).
最后一行的sum++不影响复杂度。
很明显，在您的示例 b) 中，内部循环比 a) 中的迭代次数少。在每次迭代中将迭代计数器减半本质上是对数 (log2) 运算，因此示例 b) 的 O 复杂度为 O( n log2(n)).
请注意，这并非特定于 Java - 在任何其他语言中都是相同的:-)
干杯，
从纯计算机科学的角度来看，大 O（见定义）描述了最坏的情况。这甚至意味着如果将内部 for 循环减半，O(n^2) 仍然适用。但是你可以把它写成一个不太上升的函数。
首先：Big O 表示法与编程语言无关，它只取决于实现。因此，如果您使用 Java 或任何其他语言执行循环是无关紧要的（除了 interpreter/compiler 执行的一些优化之外，这将改变程序流程）
对于嵌套循环：
1) sum++ 被视为成本为 1 的常量操作。因此可以忽略不计。 O(n * 1) = O(n)
2) 外环大致保持不变，O(n-1) 等于 O(n)，因为在渐近计算中总是可以忽略常数项。
3) 内部循环需要 log2(n) 步完成。每一步 n 减半，因此乘以 2 需要一步 back，这导致二进制对数。
综上所述，复杂度为O(n log2(n))
编辑：有趣的是：到目前为止还没有人看到内部循环具有 O(infinity) 的真正复杂性，因为某些正数的除法总是大于 0... 或者我错了吗？
我是 Java 的新手，我的问题是大 O 复杂性。
对于a)来说，显然是O(n^2)对于嵌套循环
for ( int i = 0; i < n; i++)
for ( int j=0; j < n; j++ )
然而，对于 b)，在末尾有 sum++ 操作，并且嵌套循环中的复杂性，是否完全改变了它的 Big-O 复杂性？
int sum = 0;
for ( int i = 1; i <= n; i++)
for ( int j = n; j > 0; j /= 2)
sum++;
在您的第二个示例中，第一个 for 迭代 n 次，第二个迭代 log2(n) 次，因为您将 j 除以 2在每次迭代中。因此，复杂度为 O(n log2 n).
sum++不影响复杂度。
很明显，在您的示例 b) 中，内部循环比 a) 中的迭代次数少。在每次迭代中将迭代计数器减半本质上是对数 (log2) 运算，因此示例 b) 的 O 复杂度为 O( n log2(n)).
请注意，这并非特定于 Java - 在任何其他语言中都是相同的:-)
干杯，
从纯计算机科学的角度来看，大 O（见定义）描述了最坏的情况。这甚至意味着如果将内部 for 循环减半，O(n^2) 仍然适用。但是你可以把它写成一个不太上升的函数。
首先：Big O 表示法与编程语言无关，它只取决于实现。因此，如果您使用 Java 或任何其他语言执行循环是无关紧要的（除了 interpreter/compiler 执行的一些优化之外，这将改变程序流程）
对于嵌套循环：
1) sum++ 被视为成本为 1 的常量操作。因此可以忽略不计。 O(n * 1) = O(n)
2) 外环大致保持不变，O(n-1) 等于 O(n)，因为在渐近计算中总是可以忽略常数项。
3) 内部循环需要 log2(n) 步完成。每一步 n 减半，因此乘以 2 需要一步 back，这导致二进制对数。
综上所述，复杂度为O(n log2(n))
编辑：有趣的是：到目前为止还没有人看到内部循环具有 O(infinity) 的真正复杂性，因为某些正数的除法总是大于 0... 或者我错了吗？