Блог

Привет, я пытаюсь решить одну проблему. У меня m * n матрица. Это целочисленная матрица только с 0 и 1.Я хочу выяснить строку, для которой сумма всех элементов будет наибольшей. Я решаю это простым решением. Я использую 2 для циклов и вычисляю сумму каждой строки. Но я хочу найти более эффективный способ сделать это. У кого-нибудь есть представление об этом. Мне нужно оптимизированное решение. Спасибо.

Давайте рассмотрим любые два элемента в разных строках матрицы. Просто выберите два, не имеет значения, какие из них, если они не находятся в одной строке. Установите все остальные элементы матрицы равными нулю. Затем мы можем выбрать, какая строка будет ответом, написав 1 в одном из выбранных нами элементов и 0 в другом.

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

Но в некоторых случаях вы можете закоротить процедуру. Предположим, что на данный момент наибольшая сумма элементов в любой строке, которую вы исследовали до сих пор, равна x . Теперь вы изучаете новую строку, содержащую n элементы. Если к тому времени, когда вы изучили k эти элементы, сумма этих k элементов меньше x - n k , то вы точно знаете, что сумма элементов в этой строке меньше x , и вам не нужно смотреть на эту строку дальше.

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