Алгоритм в списке и максимальный продукт
а) с последовательностью положительных действительных чисел последовательности X = (x1, x2, …, xn) мы можем найти подпоследовательность, в которой элементы в этой подпоследовательности имеют максимальное произведение в O (n).
б) с помощью алгоритма порядка O (n) мы можем объединить m = sqrt (n) отсортированных последовательностей, которые в целом имеют n элементов.
почему мой профессор говорит, что эти два предложения ложны?
я прочитал O (N) алгоритмы для (а):
http://www.geeksforgeeks.org/maximum-product-subarray/
кто-нибудь может мне помочь?
Решение
Я не знаю о первом утверждении, но второе утверждение можно сказать ложным с помощью следующего аргумента:
Поскольку существуют последовательности sqrt (n), каждая из которых содержит n элементов, общее количество элементов в n * sqrt (n). В худшем случае вам нужно будет проверить каждый элемент хотя бы один раз, чтобы объединить их все в один список, и это повысит временную сложность как минимум n * sqrt (n). Если в каждой последовательности есть элементы sqrt (n), пожалуйста, прочитайте правку.
Я не совсем уверен насчет первого, потому что предоставленный вами алгоритм предназначен для целых чисел, в то время как мы имеем дело с реалами в вашем случае.
РЕДАКТИРОВАТЬ: алгоритм объединения для k отсортированных массивов и n полных элементов устанавливает сложность времени в O (n * log (k)). Даже если каждая последовательность имеет элементы sqrt (n) (в отличие от n каждого, как предполагалось в предыдущем абзаце), временная сложность все равно будет O (n * (log (sqrt (n))))).
Другие решения
detector