在小于O（n ^ 2）的时间内填充2d阵列 [英] Filling 2d array in less than O(n^2) time
问题描述
标准的2d数组填充越来越多的行和列：
for（int i = 0; i< n; i ++）
for（ int j = 0; j< n; j ++）
a [i] [j] = i + j;
问题是它是O（ N ^ 2）。我正在寻找一种减少时间的方法，
有什么建议吗？我正在使用谷歌搜索动态编程解决方案，但
没有提出太多。
standard 2d array filling with increasing numbers for rows and columns:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j] = i + j;
problem is it''s O(n^2). I''m looking for a method to decrease the time,
any suggestions? I''m googling for dynamic programming solutions, but
not coming up with much.
推荐答案
pj*****@gmail.com 写道：
标准的2d数组填充越来越多的数字对于行和列：
for（int i = 0; i< n; i ++）
for（int j = 0; j< n; j ++）
a [i ] [j] = i + j;
问题是它是O（n ^ 2）。我正在寻找减少时间的方法，
任何建议？我正在使用谷歌搜索动态编程解决方案，但
没有提出太多。
standard 2d array filling with increasing numbers for rows and columns:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j] = i + j;
problem is it''s O(n^2). I''m looking for a method to decrease the time,
any suggestions? I''m googling for dynamic programming solutions, but
not coming up with much.
我不认为这是可能的，因为你必须*分配n ^ 2个元素。
I don''t think it''s possible, since you *must* assign n^2 elements.
red floyd写道：
red floyd wrote:
pj ***** @ gmail.com 写道：
标准的2d数组填充行和列的数字越来越多：
for（int i = 0; i< n; i ++）
for（int j = 0; j< n; j ++）
a [i] [j] = i + j;
问题是它是O（n ^ 2）。我正在寻找减少时间的方法，
任何建议？我正在谷歌搜索动态编程解决方案，但是没有提出太多。
standard 2d array filling with increasing numbers for rows and columns:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j] = i + j;
problem is it''s O(n^2). I''m looking for a method to decrease the time,
any suggestions? I''m googling for dynamic programming solutions, but
not coming up with much.
我不认为这是可能的，因为你*必须*分配n ^ 2个元素。
I don''t think it''s possible, since you *must* assign n^2 elements.
是的，这个算法不是O（n ^ 2）。它是O（n），并且可以是高效的
（理论上）。
Ryan
Yes, this algorithm is not O(n^2). It is O(n), and as efficient
(theoretically) as can be.
Ryan
rwf_20写道：
red floyd写道：
red floyd wrote:
pj ***** @ gmail.com写道：
pj*****@gmail.com wrote:
标准的2d数组填充行和列的数字越来越多：
for（int i = 0; i< n; i ++）
for（int j = 0; j< n; j ++）
a [i] [j] = i + j;
问题是它是O（n ^ 2）。我正在寻找减少时间的方法，
任何建议？我正在谷歌搜索动态编程解决方案，但是没有提出太多。
standard 2d array filling with increasing numbers for rows and columns:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j] = i + j;
problem is it''s O(n^2). I''m looking for a method to decrease the time,
any suggestions? I''m googling for dynamic programming solutions, but
not coming up with much.
我不认为这是可能的，因为你*必须*分配n ^ 2个元素。
I don''t think it''s possible, since you *must* assign n^2 elements.
是的，这个算法不是O（n ^ 2）。它是O（n），并且在理论上可以是有效的。
Yes, this algorithm is not O(n^2). It is O(n), and as efficient
(theoretically) as can be.
你是否愿意解释它是如何O（n ），而不是O（n ^ 2）？
Would you care to explain how it''s O(n), and not O(n^2)?
这篇关于在小于O（n ^ 2）的时间内填充2d阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
