algorithm - Big-O分析-3种不同时间复杂性的即时陈述

下面是一个例子int i;for(i=0;i<n;i++){ if(IsSignificantData(i)) SpecialTreatment(i);}IsSignificantData（i）是O(n)特殊处理（i）是O(n log n)1.Big-O结果是否n^2因为它是n*n，其中第一个n是for loop的Big-O，另一个n是IsSignificantData的Big-O？2.在这种情况下，总是使用if语句中最坏的情况乘以for循环吗？ 最佳答案 这要看情况。由于不知道IsSignificantData的行为（除了它是o（n）），我们可以说的最多的算法是o（n~logn）。因为在最坏的情况下，IsSignificantData始终返回true，然后算法与for(i=0;i<n;i++){ IsSignificantData(i); SpecialTreatment(i);}O（n logn）的阶数大于O（n），因此IsSignificantData基本上不相关然后循环使其为o（n？logn）。如果IsSignificantData返回true随机半个时间，或交替true和false，或一个true每千次，则相同的论点适用于：在任何情况下，true s的数目与调用函数的次数成正比，复杂性为O（nlog log n）。另一方面，如果IsSignificantData(i)返回true仅为一个值（或任何固定数值），则算法的复杂度为O（n）。这是因为复杂性是调用 n次（即O（n）），加上调用一次（或一些固定次数）的总和。i为O（n logn），其阶数低于O（n~2）。还有其他的可能性但是，在给定信息的情况下，可以肯定的是，算法绝对是o（n~logn）。