C++ 数据复杂度
这里n>=c/d,cn<=dn^2怎么求出来的？？？
还有n>=max{n1,n2,c/d}这里怎么推导出来P比Q快
回答：
这是需要证明的是存在性。即证明，对于任意f属于Θ(n)，任意g属于Θ(n^2)，存在nx，对任意n>=nx，有f(n)<g(n)。
n>=c/d,cn<=dn^2怎么求出来的？
由Θ的定义可知，存在n1，当n>=n1时，存在c使得f(n) <= cn。存在n2，当n>=n2时，存在d使得dn^2 <= g(n)。
若cn < dn^2，则 f(n) <= cn < dn^2 <= g(n)，则有f(n) < g(n) 。
即当c，d存在时，对任意n，有f(n) < g(n)的充分条件是cn < dn^2。化简后得n > c/d。
原文中用的小于等于，而当取到等号时，两个算法的耗时是一样的。
n>=max{n1,n2,c/d}这里怎么推导出来P比Q快
由于是证明存在性，只要给出一个满足条件的nx即可。这里nx需要满足对任意n>=nx，有f(n) < g(n)。
根据前面的证明，可知f(n) < g(n)，或者说P比Q快，的充分条件是c,d存在，n > c/d。
取nx为满足条件的n的下界：
对n > c/d，需nx >= ⌈c/d⌉ + 1，
对c存在，即n>=n1，需nx >= n1，
对d存在，即n>=n2，需nx >= n2。
同时满足这三个条件的nx有很多，只需给出一个nx便可证明存在性。这里取nx = max{ n1, n2, ⌈c/d⌉ + 1 }，易证nx满足这三个条件。存在性得证。
以上是 C++ 数据复杂度 的全部内容， 来源链接： utcz.com/p/190926.html
