3种不同时间复杂度的大-O分析-如果做某事声明
下面是一个例子
int i;
for(i=0;i<n;i++)
{
if(IsSignificantData(i))
SpecialTreatment(i);
}IsSignificantData(i)是O(n)
SpecialTreatment(i)是O(n log n)
1.大O成绩是n^2吗？因为它是n*n，其中第一个n是用于循环的大O，而花药n是IsSignificantData的大o。
2.在这种情况下，在if语句中总是使用最坏的情况吗？
回答 2
Stack Overflow用户
发布于 2017-09-27 14:34:14
那得看情况。
由于不知道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平方对数)。
Stack Overflow用户
发布于 2017-09-27 14:38:19
- 此代码的大O是
n*n*n log(n) -> n^3 log(n)。 - 即使您使用的是函数，您的代码实际上是以下格式： (1至n) { for(1 to n) { if (true) { for (1 to n) { some_log(n)函数} 拥有if语句并不能降低最坏情况的复杂性。
https://stackoverflow.com/questions/46450270
复制相似问题
腾讯云开发者
