Выполняется ли добавление к переменной в al oop со сложностью O (n ^ 2)?

Question

Этот фрагмент был взят из примера DataCamp:

for (log in logs) {
 info <- c(info, log$timestamp)
}

Я новичок в R, но мне кажется, что это работает с временной сложностью O (n ² ) ( что означает, что удвоение размера ввода приведет к тому, что он будет работать в 4 раза дольше).

Неужели? И если да, то как можно итеративно наращивать info быстрее?

Answer 1

Вы посещаете каждый элемент в logs один раз в течение l oop, поэтому этот код работает с временной сложностью O (n). O (n ² ) будет, если для каждого элемента в списке вы посетили каждый другой элемент в списке, то есть:

for (log in logs) {
 for (log in logs) {
  info <- c(info, log$timestamp)
 }
}

При этом, только потому, что что-то имеет линейный сложность или полиномиальная сложность не означает, что это хорошая идея (хотя при прочих равных одно определенно лучше, чем другое). Есть и другие факторы, которые следует учитывать, например, насколько эффективен каждый отдельный шаг в итерации или насколько велика ваша коллекция.

Временная сложность может рассказать вам общую историю, но не все. Может быть другой подход к выполнению той же операции, который имеет такую ​​же (или даже хуже) временную сложность, но имеет гораздо лучшую операционную эффективность, что приводит к более быстрому общему алгоритму. Например, код info <- sapply(logs, `$`, "timestamp"), который r2evans предоставил в своем комментарии, предположительно имеет такую ​​же временную сложность, но обрабатывает всю коллекцию более эффективно и избавит вас от необходимости явно создавать al oop.