制定出F（N），单位时间作业的确切数量每道工序需要作为输入大小n的函数 [英] work out f(n), the exact number of unit-time operations each procedure requires as a function of the input size n

问题描述

我有这2个问题 - 我相信一人早前公布 - 但无人接听。 我想我已经回答了：第二个正确的......

有什么建议？

工作出F（N），单位时间作业的确切数量每道工序需要为 输入尺寸为n的功能

 （一）对于i LT -1到n做
 为J＆LT; -1到2N-怎么办
//单价操作
  ------------------------------（我）这是我一个我需要一些帮助。
（二）对于i LT -1到n做
 对于j＆所述;  -  2至第（n + i）办理
//单价操作

对于i：1到n做：
 对于j：2到n +我做的：
  单元
 

现在，假设N = 1

  I = 1;约：2到2 = 1次
 共1台

  N = 2

I = 1;约：2〜3 = 2倍
I = 2;约：2-4 = 3倍
 总：2 + 3 = 5台

 N = 3

I = 1;约：2-4 = 4倍
I = 2;约：2〜5 = 5倍
I = 3;约：2-6 = 6倍
总：4 + 5 + 6 = 10个单位

  模式是F（N）= N ^ 2 + 1，是这样吗？
 

解决方案

有关你提到，你可以使用的情况下（情况下（i）段）的算术级数

在这种情况下，作为第一项= 2 * N-1，最后一项为n，因此所有条款的总和

S = N / 2 *（N + 2 * N-1）=为O（n ^ 2）

对于案例二，第一项=（N + 1-1）= n和最后一项=（N + N-1）=（2 * N-1），因此总和，S等于，

S = N / 2（第一项+最后一个学期）= N / 2 *（N + 2 * N-1）=为O（n ^ 2）

您必须观察到，S代表两个（ⅰ）及（ⅱ）相同。

I have these 2 questions - I believe one was posted earlier - but was unanswered. I think I have answered 2nd one correctly ...

Any suggestions ?

work out f(n), the exact number of unit-time operations each procedure requires as a function of the input size n

(i) for i<-1 to n do
 for j<-1 to 2n-i do
//a unit cost operation
  ------------------------------ (i) this is i the one i need some help on.
(ii) for i <-1 to n do
 for j <- 2 to (n+i) do
// a unit cost operation

for i: 1 to n do:
 for j: 2 to n + i do:
  unit

now, let's say n=1

 i=1; j: 2 to 2 = 1 times
 total: 1 units

  n=2

i=1; j: 2 to 3 = 2 times
i=2; j: 2 to 4 = 3 times
 total: 2 + 3 = 5 units

 n=3

i=1; j: 2 to 4 = 4 times
i=2; j: 2 to 5 = 5 times
i=3; j: 2 to 6 = 6 times
total: 4 + 5 + 6 = 10 units

  Pattern being f(n) = n^2 +1 , is that right?

解决方案

For the case you mentioned(case (i)) you can use Arithmetic Progressions

In this case as first term=2*n-1 and the last term is n, so sum of all the terms is

S=n/2*(n+2*n-1)=O(n^2)

For the Case II, first term=(n+1-1)=n and last term=(n+n-1)=(2*n-1), so Sum, S is equal to,

S=n/2(first term+last term)=n/2*(n+2*n-1)=O(n^2)

You must have observed that S for both (i) & (ii) are same.

这篇关于制定出F（N），单位时间作业的确切数量每道工序需要作为输入大小n的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！