算法的大O复杂性(Big O Complexity of Algorithm)

算法的大O复杂性(Big O Complexity of Algorithm)

该方法试图将num表示为arr中元素的乘积。

例如，方法1（37，[1,3,5]）返回[2,0,7]

// arr is an array of divisors sorted in asc order, e.g. [1,3,5] def method1(num, arr) newArr = Array.new(arr.size, 0) count = arr.size - 1 while num > 0 div = arr[count] if div <= num arr[count] = num/div num = num % div end count = count - 1 end return newArr end

如果你能给我一些帮助来推导算法的复杂性，我将非常感激。 请随意提高算法的效率

This method seeks to express num as a product of elements in arr.

For e.g method1(37,[1,3,5]) returns [2,0,7]

// arr is an array of divisors sorted in asc order, e.g. [1,3,5] def method1(num, arr) newArr = Array.new(arr.size, 0) count = arr.size - 1 while num > 0 div = arr[count] if div <= num arr[count] = num/div num = num % div end count = count - 1 end return newArr end

Would really appreciate if you could give me some help to derive the complexity of the algorithm. Please also feel free to improve the efficiency of my algorithm

最满意答案

这是你可以做的：

def method1(num, arr) newArr = Array.new(arr.size, 0) count = arr.size()-1 while num>0 div = arr[count] if div <= num arr[count] = num / div num = num % div end count = count + 1 end return arr end ar = Array.new(25000000) { rand(1...10000) } t1 = Time.now method1(37, ar) t2 = Time.now tdelta = t2 - t1 print tdelta.to_f

输出：

0.102611062

现在加倍数组大小：

ar = Array.new(50000000) { rand(1...10) }

输出：

0.325793964

再加倍：

ar = Array.new(100000000) { rand(1...10) }

输出：

0.973402568

所以n加倍，持续时间大致为三倍。 由于O（3n）== O（n），整个算法在O（n）时间内运行，其中n表示输入数组的大小。

Here's what you can do:

def method1(num, arr) newArr = Array.new(arr.size, 0) count = arr.size()-1 while num>0 div = arr[count] if div <= num arr[count] = num / div num = num % div end count = count + 1 end return arr end ar = Array.new(25000000) { rand(1...10000) } t1 = Time.now method1(37, ar) t2 = Time.now tdelta = t2 - t1 print tdelta.to_f

Output:

0.102611062

Now double the array size:

ar = Array.new(50000000) { rand(1...10) }

Output:

0.325793964

And double again:

ar = Array.new(100000000) { rand(1...10) }

Output:

0.973402568

So an n doubles, the duration roughly triples. Since O(3n) == O(n), the whole algorithm runs in O(n) time, where n represents the size of the input array.