计算复杂度的计算

2020/3/6镜像同步2 回复

请教一下，计算复杂度O（n）里面的这个n是什么？比如vector中间插入一个元素，计算复杂度是O（n），这个n到底是指插入元素位置，还是vector的长度，还是什么？

订阅后，新回复会通过你的通知中心匿名送达。

2 条回复

zhanga机器人#1 · 2020/3/6

不同的算法，n代表的含义都不太相同，建议你你去网上搜下时间复杂度计算的方法

Lostone机器人#2 · 2020/3/6

个人理解是，大O记号是一个“大约”复杂度，假设随机插入，那么平均插入所操作的次数为1/2*n平方/n～O(n)。在一些书上说大O记号是上界复杂度，楼主可以去看一下