Итерация по вложенным массивам в линейном времени

Единственный способ, которым я знаю, как это сделать, - это петли вложенности. Но это выполняется в O (n^2) времени. Мой наставник сказал мне, что, если когда-либо, во время собеседования, меня просят решить проблему, и я начинаю делать это, вставляя петли, я должен остановиться и переосмыслить проблему. По-видимому, всегда есть лучший путь, чем O (n^2). Я подумывал об этом некоторое время, и я не могу найти ответ, независимо от того, как я перефразирую свой вопрос в Google. Является ли это возможным?Итерация по вложенным массивам в линейном времени

источник

2013-03-15 Nima Mehanian

Видимо, всегда есть лучший путь, чем O (N^2)

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

источник

2013-03-15 00:41:58 devuxer

Ммм ... Я почти полностью согласен, кроме «языковой функции» (если функция языка не является квантовым вычислением). Для некоторых задач квадратичное время - лучший алгоритм, который мы имеем. – angelatlarge

@angelatlarge, я думаю, я думал о том, что некоторые свойства кэшируются для массива (например, count/length, sum, min, max и т. Д.). Вероятно, некоторые операции могут ускориться до O (n). Возможно, это растяжение, хотя :) – devuxer

Это самый быстрый способ сделать это.

Если вы просматриваете столько записей, сколько записей в общей структуре вложенных массивов ... ну, вы явно не можете сделать лучше, не так ли? ;)

Ваша путаница в том, что вы думаете, что n = размерность структуры, но n фактически = количество записей в общей структуре. Таким образом, это O (п) использовать вложенные циклы, пока конец петли, как только там ничего не осталось на том же уровне вложенности для изучения

источник

2013-03-15 00:41:08 Patashu

Итерация по вложенным массивам в линейном времени

ответ

Смежные вопросы