关于Insertion-sort的时间复杂度

问题描述 投票:-1回答:1

Lecture note这是我的讲义,我无法弄清楚为什么当j = 2到n时,这个操作的时间是n?为什么时间不是n-2?这是我的理由,如果j = 2&n = 3,在这种情况下外循环只运行一次。如果讲座说的时间是n,那么上面例子的时间是3,但它实际只运行一次。请帮忙。

time-complexity insertion-sort
1个回答
0
投票

是的,你是对的,但我们正在计算渐近的复杂性。

随着n变得非常大,与n的因子相比,恒定因子开始变得越来越少。对于大n,2n和n ^ 2之间的差异比2n和3n之间的差异更重要。因此,为了简化事情,我们可以放弃常数因子,我们留下O(n)。 source

© www.soinside.com 2019 - 2024. All rights reserved.