请问老师，数组已满先resize再增加元素，时间复杂度是不是O(2n)=O(n)?

首页课程实战体系课手记专栏慕课教程

请问老师，数组已满先resize再增加元素，时间复杂度是不是O(2n)=O(n)?

来源：2-8 简单的复杂度分析

rannrann

2019-04-17

最坏情况，遍历两遍数组的时间复杂度是O(2n)吧

请问老师，这个想法是对的么？

写回答

1回答

liuyubobobo

liuyubobobo

2019-04-17

抱歉，我没有理解你的意思，为什么要遍历两遍数组？哪两遍？

0

2

liuyubobobo

回复

rannrann

你可以写O(2n)，但其实在大O面前，常数项是没有意义的。O(2n) = O(n)，所以你说O(n)就可以了：）

2019-05-08

共2条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

哈希表复杂度问题

回答 1

优先队列时间复杂度

回答 1

addFirst(E e)=O(n)是如何计算出来的呢?

回答 2

关于testQueue时间复杂度测试的问题

回答 1

线段树空间复杂度问题

回答 1

打开慕课网App查看更多内容