插入和大 O 符号
Insert and big O notation
我是 C 语言编程的新手。我对数组中的插入有疑问。例如在 c 和 java 中我们不能在数组的末尾插入一个新元素，它会产生错误（例如我们初始化一个大小为 5 的数组并在末尾插入一个新元素）。在这种情况下，我们需要创建一个新数组并将前一个数组中的所有元素复制到这个数组并删除前一个数组。所以这里的 space 复杂度是 O(1)。我的问题是这里的时间复杂度是多少。在一篇博客中我看到它是 O(n)，但它不是 O(2n)。首先我们创建一个新的数组时间复杂度 O(n) 然后删除之前的数组时间复杂度 O(n) 所以总时间复杂度必须是 O(2n) ？你们能帮帮我吗...
Creating/deleting (malloc/free) 一块内存不是 O(n) 而是 O(1) 复杂度。 Copying/moving 从一个内存块到另一个内存块的元素是 O(n)。
如果你必须为每个元素调用一个 constructor/destructor，那么你确实会有 O(2n) 的复杂度，但如果你只是 'move' 个元素，那么复杂度将是 O( n).
但是就像上面评论中的用户prog-fh一样，O(2n)是O(n)。
注意：在C中，可以通过memcpy复制一块内存，我只考虑了元素方式（例如调用元素复制函数或元素方式赋值操作）。
是的，你在技术上是正确的。在此之前，我们必须了解用于时间复杂度的符号。
Big-O 表示法：O(n) 只是上限（最坏情况）的近似值，而不是精确值，这意味着，它可以等于 O( c.n)。
这里正如你所说的 c 是 2.
所以一个粗略的近似是O(n)。了解我们使用的符号只是近似值。
关于时间复杂度和符号的有用文章：here
我是 C 语言编程的新手。我对数组中的插入有疑问。例如在 c 和 java 中我们不能在数组的末尾插入一个新元素，它会产生错误（例如我们初始化一个大小为 5 的数组并在末尾插入一个新元素）。在这种情况下，我们需要创建一个新数组并将前一个数组中的所有元素复制到这个数组并删除前一个数组。所以这里的 space 复杂度是 O(1)。我的问题是这里的时间复杂度是多少。在一篇博客中我看到它是 O(n)，但它不是 O(2n)。首先我们创建一个新的数组时间复杂度 O(n) 然后删除之前的数组时间复杂度 O(n) 所以总时间复杂度必须是 O(2n) ？你们能帮帮我吗...
Creating/deleting (malloc/free) 一块内存不是 O(n) 而是 O(1) 复杂度。 Copying/moving 从一个内存块到另一个内存块的元素是 O(n)。
如果你必须为每个元素调用一个 constructor/destructor，那么你确实会有 O(2n) 的复杂度，但如果你只是 'move' 个元素，那么复杂度将是 O( n).
但是就像上面评论中的用户prog-fh一样，O(2n)是O(n)。
注意：在C中，可以通过memcpy复制一块内存，我只考虑了元素方式（例如调用元素复制函数或元素方式赋值操作）。
是的，你在技术上是正确的。在此之前，我们必须了解用于时间复杂度的符号。
Big-O 表示法：O(n) 只是上限（最坏情况）的近似值，而不是精确值，这意味着，它可以等于 O( c.n)。 这里正如你所说的 c 是 2.
所以一个粗略的近似是O(n)。了解我们使用的符号只是近似值。
关于时间复杂度和符号的有用文章：here