5
Учитывая массив целых чисел, написать метод, который возвращает все уникальные пары, которые добавляют до 100.Какова сложность моего кода Big-O?
Пример данных:
sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]
Я решал эту проблему в эти выходные, и в то время как мое решение кажется масштабируемой и Я хотел бы определить, какова наихудшая временная сложность моего решения?
Вот мое решение:
def solution(arr)
res = []
h = Hash.new
# this seems to be O(N)
arr.each do |elem|
h[elem] = true
end
# how do I determine what Time complexity of this could be?
arr.each do |elem|
if h[100-elem]
h[100-elem] = false
h[elem] = false
res << [elem, 100-elem]
end
end
res
end
Если обе петли O (N) каждый, и добавить их: O (N + N), это будет равна O (2N) и принимая 2 чтобы быть константой, могу ли я предположить, что мое решение O (N)?
Это было бы правильно. – screenmutt
Я думаю, что ваши предположения в основном верны. Это также предполагает, что элементы могут быть отрицательными (и более 100), чтобы это имело смысл - в противном случае только дедупликация исходного ввода имеет любую стоимость масштабирования, а все остальное можно рассматривать как фиксированную стоимость, как только вы заполняете все ключи 0 .. 100. Технически 'h [elem] = true' не является' O (1) '(что многие люди считают), но« O (log (N)) », поэтому ваша общая сложность, вероятно,« O (Nlog (N)) 'худший случай - вы только видите, что если вы перекачиваете массивы с миллионами целых чисел, то –
@NeilSlater Вы неверны. 'h' - это хеш-карта, поиск которой является линейным временем. [Wiki] (http://en.wikipedia.org/wiki/Hash_table) – screenmutt