开发者

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

开发者 https://www.devze.com 2023-02-16 16:48 出处:网络
I have this question to solve, but despite my efforts, there is no result开发者_如何学编程 so far.

I have this question to solve, but despite my efforts, there is no result开发者_如何学编程 so far.

for i  <− 1 to n do
           for j  <− 2 to (n+i) do
                 // a unit cost operation

and also

for i  <− 1 to n do 
            for j  <− 1 to n do
                           for k <− 1 to (i+1) do

Any suggestions for solving it are welcome.


Try this: pick some small n (say n = 5), and for each "unit cost operation" put a tally mark on a piece of paper. Count them. As you are tallying, you should notice the pattern that you need to solve it.


1st one

first lets format.

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 = 7 times
  • i=2; j: 2 to 5 = 8 times
  • i=3; j: 2 to 6 = 9 times

total: 7 + 8 + 9 = 24 units

Pattern emerging yet?..

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号