如数组中有n个元素,用冒泡算法排序,最坏情况下是数组中元素全部倒序,排序需通过n-1趟比较,每趟比较需n-1
次比较,这样算来,时间复杂度岂不是(n-1)的平方,为什么是n的平方?

解决方案 »

  1.   

    N只是一个替代符号,重要的还是那个指数(平方)。
    可以这样理解 - 对于一定规模的问题,O(N*N)的算法可以在平方时间的这个级别下完成。
      

  2.   

    (n-1)的平方 =  n平方 - 2n +1
    当n趋向无限大, 那么它的值就趋向于n平方, (-2n+1)可以忽略掉
      

  3.   


    up n 只是 时间级别
      

  4.   

    在描述复杂度 o(n^2) 的时候,有一个小o,不要忽略了这个小o的含义。o(n^2) 跟 o((n-1)^2) 是完全相等的。
      

  5.   

    LZ刚开始学习数据结构么?这个问题可以跟你老师讨论一下,看看他怎么跟你解释。这个N就是一个概念上的,不能具体化。
      

  6.   

    呵呵,你说是N大,还是N-1大(n->无穷大)