使用 2 种不同方法时的 O(N) 差异很大

Question

我的问题如下：

我有一个函数可以操作 MAX 元素数组的内容。这个函数看起来像下面这样：

    //GLobal Variables
    uint8_t my_array[ MAX ];
    #define EMPTY 0xFF

    ...
    void initArray( void )
    {
        for( uint8_t i=0; i<MAX; i++ )
        {
             my_array[ i ] = EMPTY;   
        }
    }
    void manipulateArray( uint8_t value )
    {
        for( uint8_t i=0; i<MAX; i++ )
        {
             if( EMPTY == my_array[ i ] )
             {
                  my_array[ i ] = value;
                  break;
              }
        }
    }

    ...

    int main( void )
    {
         ...
         initArray();
         ...
         while( false == exit_flag )
         {
               manipulateArray( value );
               //get new value from user
               //update exit_flag based on new value
         }
         ...
         return 0;
    }

但后来我想，如果我最终做了很多 insertion/deletion，那么我会疯狂地使用 for 循环，这势必会影响程序的速度或大 O(N)。所以我想如果我使用另一个全局

用于跟踪数组中下一个空运动的插入位置的变量，而不是每次都循环遍历它：

//GLobal Variables
uint8_t my_array[ MAX ];
uint8_t idx = 0;

...

void manipulateArray( uint8_t value )
{
    my_array[ idx++ ] = value;
}

我的假设是否正确？同样，在这种特殊情况下使用更适合操作性质（大量插入和少量删除）的另一种数据结构是否会更好：向量、链表...

提前致谢，

Answer 1

笼统地解释你，我认为你是在询问 "inserting" 值覆盖 EMPTY 值的问题，以及将 "deleting" 值替换为 [=10] 的问题=].在这种情况下，您建议维护一个跟踪下一个 "empty" 位置的全局变量，以避免必须在数组中搜索该位置。

确实，如果你知道下一个插入位置的位置，那么你可以在 O(1) 步内执行插入，而如果你需要执行线性搜索，最好的边界是 O(n ).如果您总是在数组的（非空部分）末尾插入或删除，那么按照您的建议维护元数据是一个非常好的策略，因为这样您就可以在 O(1) 步骤中维护辅助变量，也是。

但是假设您需要支持从任意位置删除，而不移动其他数组元素，并且您还希望能够使用插入函数重新填充这些位置。在那种情况下，您必须解决维护有关多个空位置位置的信息的问题。单个标量变量是不够的，依赖数组本身需要你在数组中搜索空位置，这又回到了你开始的地方。

另一种方法是使用更复杂的数据结构——例如数组或链表——来跟踪主数组中的开口。通过这种方式，您可以在任何序列的任何位置进行任意数量的插入和删除，实现 O(1) 的复杂度，代价是使用 O(n) memory 来维护有关的元数据开阵阵地。这是典型的 space 与速度权衡：实现更快的算法需要使用更多内存，但您可以通过使用更慢的算法来节省内存。

使用 2 种不同方法时的 O(N) 差异很大

Big O(N) difference while using 2 different appraoches

c

c++

big-o

loops