如何计算此算法中的原始运算? [英] How do I count primitive operations in this algorithm?

问题描述

首先:以下伪代码的 T(n)是什么，因此是 O(n)?当内部for循环具有变量限制时，如何对此类代码进行操作并计数?

Firstly: What is the T(n), and thus O(n) of the following Pseudo-Code? How can I go through and count operations for code like this when the inner for-loop has a variable limit?

其次:当我努力准确地计算它们时，需要寻找哪些原始操作.

Secondly: What are the primitive operations to look for as I am struggling to count them exactly.

我知道没有必要计算原始操作的确切次数(对于 O(n))，但是知道如何进行操作，这将使我更轻松地计算出大图景"

I understand it isn't necessary to count the exact number of primitive operations (for O(n)) but knowing how to do so that would make me more comfortable calculating the 'big picture'.

Input: X, a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n ~T1 = 1 or n  
2) For i = 0 to n-1                               ~T2 = n (multiplies T3 to T8)                     
3)    Let s = X[0]                                ~T3 = 1                     
4)    For j = 1 to i                              ~T4 = ? multiplies T5                     
5)       Let s = s + X[j]                         ~T5 = 2 reads and 1 set? Or 1 operation if using +=?                     
6)    End For                                     ~T6 = 0                   
7)   Let A[i] = s /(i+1)                          ~T7 = 1 set and 1 or 2 reads                     
8) End For                                        ~T8 = 0  
Output: An n-element array A of numbers such that A[i]
        is the average of elements X[0],X[1], … ,X[i]

任何能提高原始操作计数(包括答案​​)的材料/资源/问题都将受到赞赏.

Any materials/resources/Qs that sharpen primitive operation counting (with answers) are greatly appreciated.

推荐答案

因此，解决此问题的最简单方法似乎是立即计算出每一行的总数，而不是事后相乘.澄清如下:

So it seems the easiest way to break this problem down is by working out the total for each line immediately, rather than multiplying afterwards. The clarifications are:

• T ₁ 设置任意大小的数组是 1 操作
• T ₂ For循环的设置为i的范围: n
• T ₃ 1次读取加上1个设置时间n， 2n
• T ₄ 使用第二个上的第一个for循环的逻辑，并向小n计数而不是立即尝试相乘，我们看到我们有0(由于对于j = 1到0 是没有意义的)+ 1 + 2 + ... +(n-1).现在我们使用著名的Sum公式S _x = x(x + 1)/2，除了这里我们使用n-1之外，因此S _n-1 =(n-1)(n-1 + 1)/2 = (n ² -n)/2
• T ₅ 被读取+读取+添加+设置，进行4次操作，乘以它的立即 for 循环，得到 2(n ² -n)
• T ₆ 为0，因为它只是标记 for 循环的结尾
可以猜出(li> T ₇ 从左到右(不确定):set + read + divide + read + add，5个操作，乘以外部 for 循环的大小，表示 5n
• T ₈ 参见T ₆

• T₁ Setting an array of any size is 1 operation
• T₂ The setting of a For loop is the range of i: n
• T₃ 1 read plus 1 set times n, 2n
• T₄ Using the logic of the first for loop on the secondary one and counting towards a small n instead of trying to multiply immediately, we see we'd have 0 (discounted because for j=1 to 0 makes no sense) + 1+2+...+(n-1). Now we use the famous Sum formula S_x=x(x+1)/2 except here we're using n-1 so S_n-1 = (n-1)(n-1+1)/2 = (n² - n)/2
• T₅ is read+read+add+set, 4 operations, times it's immediate for loop giving 2(n²-n)
• T₆ is 0 as it's just marking the end of the for loop
• T₇ can be guessed (not certain) as going left to right: set+read+divide+read+add, 5 operations, times the outside for loop's size which means 5n
• T₈ see T₆

THUS在1到n之间加上T _n 使我们没有吸引力:

THUS adding T_n for 1 to n gives us the unattractive:

T(n)= 1 + 5.5n + 2.5n ²

T(n) = 1 + 5.5n + 2.5n²

O(n ² )

TL; DR:分别计算每行，使用前n个自然数公式的和，如果太难抽象，则使用小n.

TL;DR: work out each line individually, use sum of first n natural numbers formula, use small n if too difficult to do in abstract.

最初，这使我感到困惑，因为我正在使用T(n)的非整数系数，但结果始终是Integer:)

这篇关于如何计算此算法中的原始运算?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！