问个关于时间复杂度的有关问题
问个关于时间复杂度的问题
最近在看国外的公开课，讲到时间复杂度，我原以为O的算法就是只保留函数中最高项，并且去除其系数和其他低阶项。
例如：1000n^2 + 50n = O(n^2)
公开课中，给这种算法一种明确的数学定义，如果存在正的常数C和自然数N0，使得当N>N0时有f(N)<C*g(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。
举例：因为对所有的N>1，有3N<4N，所以有3N=O（N）；
这个计算过程是没有问题的，但他还有一个举例。
举例：因为对所有N>1，有N^2<N^3，所以有N^2=O(N^3)
问题是：按照数学定义,C取2，N^2<2*N^2,所以有N^2=O(N^2)，这样为什么不对呢？
------解决方案--------------------
计算原理里面的内容，大O小o是有区别的。没有为什么，就是这么定义的，理解下定义就知道了。
N^2=o(N^3)这里应该是小o
------解决方案--------------------
最详细的可以参考经典书籍：算法导论（第二版）中文版第30页左右。
那地方其实写大O与小o都对：n^2 = O(n^3)表示后者是前者的一个上界，但不是渐近紧的（注意大O既可以表示渐近紧的上确界，又可以表示非渐近紧的上界）；而2n^2 = o(n^3)表示的是一个非渐近紧的界（注意小o只能表示非渐近紧的上界）。
所以，个人认为，为区别二者，平时应该注意些，分析的时候就用大O表示紧的上确界，小o表示非紧的上确界。这样比较好，不易混
------解决方案--------------------
问题是：按照数学定义,C取2，N^2<2*N^2,所以有N^2=O(N^2)，这样为什么不对呢？
这也是对的。N^2=O(N^2)和N^2=O(N^3)同时成立。这个=O()符号严格来说是不严谨的，不过为了表示上的方便大家都这么写。
最近在看国外的公开课，讲到时间复杂度，我原以为O的算法就是只保留函数中最高项，并且去除其系数和其他低阶项。
例如：1000n^2 + 50n = O(n^2)
公开课中，给这种算法一种明确的数学定义，如果存在正的常数C和自然数N0，使得当N>N0时有f(N)<C*g(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。
举例：因为对所有的N>1，有3N<4N，所以有3N=O（N）；
这个计算过程是没有问题的，但他还有一个举例。
举例：因为对所有N>1，有N^2<N^3，所以有N^2=O(N^3)
问题是：按照数学定义,C取2，N^2<2*N^2,所以有N^2=O(N^2)，这样为什么不对呢？
------解决方案--------------------
计算原理里面的内容，大O小o是有区别的。没有为什么，就是这么定义的，理解下定义就知道了。
N^2=o(N^3)这里应该是小o
------解决方案--------------------
最详细的可以参考经典书籍：算法导论（第二版）中文版第30页左右。
那地方其实写大O与小o都对：n^2 = O(n^3)表示后者是前者的一个上界，但不是渐近紧的（注意大O既可以表示渐近紧的上确界，又可以表示非渐近紧的上界）；而2n^2 = o(n^3)表示的是一个非渐近紧的界（注意小o只能表示非渐近紧的上界）。
所以，个人认为，为区别二者，平时应该注意些，分析的时候就用大O表示紧的上确界，小o表示非紧的上确界。这样比较好，不易混
------解决方案--------------------
问题是：按照数学定义,C取2，N^2<2*N^2,所以有N^2=O(N^2)，这样为什么不对呢？
这也是对的。N^2=O(N^2)和N^2=O(N^3)同时成立。这个=O()符号严格来说是不严谨的，不过为了表示上的方便大家都这么写。