为什么这个O(n * m)的时间复杂性？
我在练习使用RAM模型计算大Oh方法，并且我很难理解为什么这个方法的总时间复杂度是n*m(n指循环迭代次数)。据我所知，方法中的前两行只是常量，时间循环的复杂性为O(n *，但每次迭代的循环中有许多步骤)。我理解调用.max和.min的综合复杂度为O(n^2)。所以，这不意味着整个时间复杂度计算会像这样吗？
line 1 = constants
line 2 = constants
line 3-7 = n * (n^2 + constants)
line 8 = constants
overall time_complexity = n^3 + constants = n^3下面是我正在分析的方法的源代码：
# O(n * m) naive solution
def max_windowed_range(array, window_size)
num_windows = array.length - window_size + 1
best_range = nil
num_windows.times do |i|
window = array.slice(i, window_size)
current_range = window.max - window.min
best_range = current_range if !best_range || current_range > best_range
end
best_range
end回答 2
Stack Overflow用户
发布于 2019-11-25 18:17:28
我们可以将其简化为非常数部分。
num_windows = array.length - window_size + 1
num_windows.times do |i|
window = array.slice(i, window_size)
current_range = window.max - window.min
end对于array的每个元素O(array.length)，它会两次查看一个window_size块，即2*O(window_size)。num_windows为n，window_size为m，当array.length显著大于window_size时，即O(n*m) 。我们会再谈这件事。
也许我们能更清楚地看到，如果我们拼出max和min长篇。
num_windows = array.length - window_size + 1
# n times
num_windows.times do |i|
# m times, but with a very, very low constant
window = array.slice(i, window_size)
# m times
max = window.each_with_object(nil) { |n,m|
m = n if !m && n > m
}
# m times
min = window.each_with_object(nil) { |n,m|
m = n if !m && n < m
}
current_range = max - min
endnum_windows.times从O(n)开始，其中n= num_windows。很简单。
每次迭代都获取一个大小为window_size或m的window，然后window.max和window.min必须扫描window两次。那是O(m)。这样做n次，就等于O(n*m)。
正如Fabio所指出的，array.slice(i, window_size)也是O(m)，但是它使用的是memcpy，它的常数很低，会完全被window.min和window.max淹没。我们可以忽略它。有关更多信息，请参见https://stackoverflow.com/a/394654/14660。
作为备份，我们可以插入一些数字。(我意识到我在window_size上犯了一个错误。这是一个说明性的认识，就大O的目的而言，这并不重要。另外，我很懒，不想重新计算。)
array.length = 1000
window_size = 10
num_windows = 990
990 * 2*10 = 19800 # actual
1000 * 10 = 10000 # O(n*m)这些数字不一定要匹配，只是随着比例的变化而变化。是array.length的两倍，大约是成本的两倍。
array.length = 2000
window_size = 10
num_windows = 1990
1990 * 2*10 = 39800 # actual
2000 * 10 = 20000 # O(n*m)是window_size的两倍，大约是成本的两倍。
array.length = 2000
window_size = 20
num_windows = 1980
1980 * 2*20 = 79200 # actual
2000 * 20 = 40000 # O(n*m)但是，当window_size接近array.length时，我们就越接近O(n)。
array.length = 100
window_size = 99
num_windows = 2
2 * 2*99 = 396 # actual
100 * 99 = 9,900 # O(n*m)
100 = 100 # O(n)两倍的长度和两倍的window_size，O(n*m)说我们应该翻两番。但我们只有三倍，离O(n)越来越近了。
array.length = 200
window_size = 198
num_windows = 3
3 * 2*198 = 1188 # actual
200 * 198 = 39600 # O(n*m)
200 = 200 # O(n)Stack Overflow用户
发布于 2019-11-25 18:11:38
行array.slice(i, window_size)不能被视为常量，因为array.slice将至少迭代数组一次O(m)
当您将其放入循环中时，它将生成n * m，其中
n迭代量，loopm迭代量，array.slice内循环迭代量，
迭代量
array.slice内部的迭代量可能等于[array.length, window_size].min。
行current_range = window.max - window.min仅为O(2*m)，因为min和max只迭代一次数组
因此，对于整个方法，您将得到O(n * 2m)，如果忽略常量- O(n * m)
https://stackoverflow.com/questions/59037160
复制相似问题
腾讯云开发者
