问3种不同时间复杂度的大-O分析-如果做某事声明

EN

那得看情况。

由于不知道IsSignificantData的行为(除了它是O( n) )，我们最多能说的是算法是O(n 2×log n)。因为在最坏的情况下，IsSignificantData总是返回true，然后算法与

for(i=0;i<n;i++)
{
  IsSignificantData(i);
  SpecialTreatment(i);
}

O(n log )比O(n)更有序，因此IsSignificantData基本上是无关的。然后循环使其为O(n平方对数)。

如果IsSignificantData在一半时间内随机返回true，或者交替返回true和false，或者每千次返回一个true --在任何情况下，trues的数量与调用函数的次数成正比，那么复杂度是O(n×log n)。

另一方面，如果IsSignificantData(i)只对i的一个值(或任何固定数值)返回true，则算法的复杂性为O(n平方)。这是因为复杂性是调用IsSignificantData(i) n次(即O(n平方))的总和，再加上调用SpecialTreatment一次(或某些固定次数)的总和。SpecialTreatment为O(n log )，其阶次低于O(N 2)。

还有其他的可能性。但是，可以肯定的是，在给出信息之后，算法肯定是O(n平方对数)。