pattern_algorithm

[giscus[bot]]

简单算法和数据结构

https://labview.qizhen.xyz/pattern_algorithm

[Awhitesu]

如果数组从后端插入元素的话，也就是第一种创建数组函数改变上下接线，所需的时间测试为5，大大减少了运行时间。

[ruanqizhen]

是的。从数组尾部插入或删除数据因为不需要挪动任何元素，时间复杂度为 O(1)，与索引的时间复杂度相同。所以也是一种推荐使用的高效的操作方法，只要确保没有在数组头或者中间插入删除就行。

但同样的时间复杂度，从数组尾部插入或删除数据的速度还是稍慢于“先初始化数组，再利用索引修改数组中每个元素”的速度。这是因为：

• 数组插入删除比索引修改元素要多一步操作：更新数组的长度信息。
• 系统每次给数组分配内存是会留有余量的，允许数组直接在尾部添加一定数量的数据。但如果添加的元素太多，可能就会发现后面的内存地址已经被其它变量占据了，不能直接再添加了。这时候，系统需要重新给数组分配一片更大的内存空间，然后复制整个数组到新空间。这一操作本身非常耗时，但因为不常发生，平摊到每一次插入删除操作，还是可以算作 O(1)。

[Awhitesu]

明白了，谢谢老师解答。