Можем ли мы скопировать список ссылок в массив в o (1) (оба имеют одинаковый размер n)?

Question

Можем ли мы скопировать список ссылок в массив в O (1) (оба имеют одинаковый размер n)?

т.е. нет элемента в списке ссылок и размер массива одинаков.

Answer 1

Нет ... хотя сама операция копирования является операцией O (1), она происходит N раз, поэтому сложность всей операции становится равной O (N).

Answer 2

Один короткий ответ.

Может быть, ваш вопрос не завершен и некоторые ограничения отсутствуют, но, как и раньше, ответ, очевидно, нет.

Answer 3

Нет: если нужно скопировать n элементов, вам потребуется n операций.Вы можете просмотреть список в O (n) и вставить каждый элемент в массив в O (1).Вы не можете ожидать постоянного времени для обработки переменного количества элементов.

Answer 4

номер

Если только вы немного не переопределите то, что вы считаете Linked List и Array. Технически вам нужно только сделать предварительное условие.

Если у вас было: Неизменяемые структуры

Тогда каждый Linked List может быть Array (если вы находитесь в элементе n, то O (1) - перейти к n-1 и n+1, поэтому часть "чтение" будет эквивалентна ). В этот момент, если вы отделите «содержимое» от «контейнера», вы можете скопировать Array в Array или Array в Linked List или Linked List в Array или Linked List до Linked List все в O (1). Под разделением контейнера по содержанию я имею в виду (в C #):

struct MyArray
{
    private int[] baseArray;

    public int this[int index]
    {
        get
        {
            return baseArray[index];
        }
    }
}

struct MyList
{
    private int[] baseArray;

    public Tuple<int, int> First()
    {
         return new Tuple<int, int>(0, baseArray[0]);
    }

    public Tuple<int, int> Next(Tuple<int, int> current)
    {
         return new Tuple<int, int>(current.Item1 + 1, baseArray(current.Item1 + 1));
    }
}

С конструктором, который принимает источник данных, конструктором копирования, который просто копирует ссылку на baseArray (это будет O (1), потому что мы копируем только ссылку) и все другие необходимые методы.

(пожалуйста, не отрицайте этот ответ слишком сильно. Это скорее провокация и / или нестандартное мышление)

(я использую C # struct s, чтобы указать на тот факт, что они являются очень легкими объектами. Настоящее «мясо» находится «внутри» baseArray. Эти структуры немного больше, чем ссылка + методы )