下面的操作需要多少cpu？有什么方法可以真正计算出来吗？

Question

考虑一个贯穿程序整个生命周期的 while 循环。你有一个字符串数组列表，对于数组中的每个字符串，你将把它与数组中的每个对象进行比较。

我不确定这部分是否重要，但假设每个对象都有一个 .getString() 方法，您可以将其与数组列表中的字符串进行比较。

ArrayList<String> stringArray = new ArrayList<>()
stringArray.add("hello");  // 0th element
.
.
.
stringArray.add("bye"); // mth element

while(true){
    //assume that you HAVE to instantiate a new object array every loop
    Object[] objectArray = {new object(), .....new object() };
    for(Object i : objectArray){
       if stringArray.contains(i.getString())
          return true;
       }
    }

如果我没记错的话这个操作需要O(m*n)时间？字符串 arrayList 将包含 m 个元素，而对象数组将包含 n 个元素。时间复杂度是否也会影响 cpu 的使用？

Answer 1

If i'm not mistaken this operation takes O(m*n) time? the string arrayList would have m number of elements and the object array would have an n number of elements.

是的，您在计算给定场景的时间复杂度方面是正确的（谈论 for 循环部分）。 ArrayList.contains() 方法需要 O(m) 时间来检查 ArrayList 中的 m 个元素是否存在于 ArrayList 中。此外，检查 this answer 以获取相同的证明。

并且，由于对象数组中有 n 个元素，因此净时间复杂度为 O(m*n)。

注意：- 如果你考虑整个程序（包括无限 while 循环），那么如果 none ArrayList 中的值包含任何对象数组值，然后在 while 循环的下一次迭代中再次实例化相同的对象数组。相同的 for 循环将具有 O(m*n) 最坏情况的复杂度，并且永远是相同的故事。

Does the time complexity also play a factor in cpu usage?

时间复杂度是一种算法分析方法，用于了解程序如何依赖于输入参数。所以，实际上随着元素数量的增加，时间复杂度总是会给出像 O(n) 或 O(log n) 这样的概括概念，它不会给出确切的 CPU 性能度量。它用于估计程序的输入成员如何影响程序的执行。

并且，对于大量元素，程序的实际 CPU 执行显然会更大，即使时间复杂度将被正式定义为相同。

例如，即使增加 n 的数量，二分查找的时间复杂度也是 O(log n)。它给你一个粗略的估计。如果您实际上运行该程序，环境、案例场景 (best/worst) 等其他几个因素也会发挥作用。

下面的操作需要多少cpu？有什么方法可以真正计算出来吗？

How much cpu does the following operation take? any way to truly calculate it?

java

algorithm

performance

cpu-usage

time-complexity