Big O обозначение для операции копирования

Question

Я встречал некоторый код, который определенно мог бы быть улучшен, но меня интересует нотация Big-O моих улучшений.

Их оригинальный код добавляет элемент в массив, и каждый разон делает это, он создает новый массив из n + 1 и копирует старый, например, так:

public MyType GetNewType()
{
    MyType[] tempTypes = new MyType[_types.Count + 1];
    _types.CopyTo(tempTypes, 0);
    _types = tempTypes;

   _types[types.Count - 1] = new MyType();
   return _types[types.Count - 1];
}

Насколько я понимаю, это будет операция O (n).Поэтому я переписал его следующим образом:

private int _currentIndex; //initialized in the constructor

public MyType GetNewType()
{
    if (_types.Length == _currentIndex)
    {
        MyType[] tempTypes = new MyType[_types.Length + 10];
        _types.CopyTo(tempTypes, 0);
        _types = tempTypes;
    }

   _types[_currentIndex] = new MyType();
   _currentIndex++;

   return _types[_currentIndex - 1];
}

Будет ли результат этих изменений означать, что функция теперь будет работать в O (n / 10), поскольку для нее потребуется только операция копирования каждые 10 вызовов?Или это не так хорошо работает?

Answer 1

С точки зрения обозначения Big-O сложность (n/10) будет O(n), потому что это не волнует такие маленькие константы.

Answer 2

Это обычная и хорошая оптимизация.Обычно это называется «амортизированным постоянным временем», что означает большую часть времени, это O (1) для добавления одного элемента, кроме случаев, когда это не так.Часто разработчики удваивают размер массива или, по крайней мере, умножают на 1,5, вместо простого добавления десяти элементов.

Тем не менее, в C # есть несколько прекрасных встроенных списочных классов, которые делают все это для вас,автоматически, и их использование должно быть предпочтительнее, чем использование пустых массивов, когда это возможно.

Answer 3

Амортизированное постоянное время работает, только если вы удваиваете размер массива каждый раз, когда у вас заканчиваются бесплатные элементы!Если нет, то усредненная большая запись O всегда будет O (n).

C # Реализация списка удваивает размер массива каждый раз, когда число списков равно емкости.

Чтобы выполнить вставкуМетод усреднения O (1) нужно примерно так:

MyType[] tempTypes = new MyType[Math.Max(8, _types.Length * 2)];