请问顺序表中插入结点时如平均移动次数为n/2,为什么说它的时间复杂程度O(n)而不是O(n/2)?

1个回答

  • 时间复杂度指算法执行过程中所需要的基本运算次数.你的只是一个大体评估的方式.

    ---------------------------------------------------------------------

    大O表示法是根据数据梯度产生的变化而评估.

    -----------------------------------------------------------------------

    大O表示法表示时间复杂度的时候取一个下限即可,不用那么精确.

    -----------------------------------------------------------------------------------------

    可能你认为o(N)和o(N/2)有区别,但实际上这两者对于大O表示法表示的时间复杂度来说没区别,大O表示法表示的时间复杂度关注的是数据量的增长导致的时间增长情况,o(N)和o(N/2)在数据量增加一倍的时候,时间开销都是增加一倍(线性增长).所以都认为是O(N)

    -------------------------------------------------------------------------------------------

    但是程序优化的时候就要精确评估了!能提高多少就提高多少.