线性复杂度和二次复杂度 [英] Linear complexity and quadratic complexity

问题描述

我不确定...

如果您具有可以以下列两种复杂度之一执行的代码:

If you have a code that can be executed in either of the following complexities:

1. O(n)的序列，例如:序列中两个O(n)
2. O(n²)

首选版本是可以在线性时间内执行的版本.是否会有时间使得O(n)的序列过多，并且会首选O(n²)?换句话说，语句C x O(n)是否小于?对于任何常数C，O(n²)始终为真吗?

The preferred version would be the one that can be executed in linear time. Would there be a time such that the sequence of O(n) would be too much and that O(n²) would be preferred? In other words, is the statement C x O(n) < O(n²) always true for any constant C?

为什么或为什么不呢?有哪些因素会影响条件，因此最好选择O(n²)复杂度?

Why or why not? What are the factors that would affect the condition such that it would be better to choose the O(n²) complexity?

推荐答案

我认为这里有两个问题；首先是符号的含义，其次是在实际程序上实际要测量的值

I think there are two issues here; first what the notation says, second what you would actually measure on real programs

1. 大O被限制为n->无穷大，因此就大O而言，O(n)<不论任何有限常量，O(n ^ 2)始终为真.

1. big O is defiend as a limit as n -> infinity so in terms of big O, O(n) < O(n^2) is always true regardless of any finite constants.

实际程序仅处理有限输入，因此很可能为n选择一个足够小的值，使得c * n> n ^ 2即c> n，但是严格来说，您不再要处理大O

as others have pointed out real programs only ever deal with some finite input, so it is quite possible to pick a small enough value for n such that the c*n > n^2 i.e. c > n, however you are strictly speaking no longer dealing with big O

这篇关于线性复杂度和二次复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！