История изменений
Исправление den73, (текущая версия) :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).
Давай khrundel, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).
И кстати да, операция добавления элемента в твой говномассив имеет стоимость O(N) по памяти - столько временной памяти ей понадобится для добавления в те моменты, когда массив нужно перевыделить. Если операцию по времени ещё можно амортизировать и что-то блеять про настоящий и ненастоящий рилтайм, то с памятью так не прокатывает. Гигабайт сейчас и ноль в остальное время - это не 10 байт в среднем, как ты должен бы понимать.
Исправление den73, :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).
Давай khrundel, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).
И кстати да, операция добавления элемента в твой говномассив имеет стоимость O(N) по памяти - столько временной памяти ей понадобится для добавления. Если операцию по времени ещё можно амортизировать и что-то блеять про настоящий и ненастоящий рилтайм, то с памятью так не прокатывает. Гигабайт сейчас и ноль в остальное время - это не 10 байт в среднем, как ты должен бы понимать.
Исправление den73, :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).
Давай khrundel, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).
И кстати да, операция добавления элемента в твой говномассив имеет стоимость O(N) - столько временной памяти ей понадобится для добавления.
Исправление den73, :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).
Давай khrundel, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).
Исправление den73, :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).
Давай, жду новых новостей из сказочного мира, где O(N) всегда меньше, чем O(1).
Исправление den73, :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2).
Исходная версия den73, :
Делать список массивами тебе понадобится только если нужно список читать линейно, т.е. в нем нужно что-то искать.
Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы».