0

假设有一个大小为 n 的数组 A。其中有一些元素。目标是尽可能快地打印它们。打印的顺序无关紧要。

朴素的算法将是，

print_number (A)
    for(i = 0 to n)
        print A[i]

它的时间复杂度为 O(n)

那么下面的呢？

print_number (A, l, r)
if (l == r)   // terminating condition
    print A[i]
else
    mid = (l+r)/2
    print_number (A, l, mid)
    print_number (A, mid, r)

这将是 O(n)

[编辑]如果我们使用并行性，假设有足够的处理器。

print_number (A, l, r)
if (l == r)   // terminating condition
    print A[i]
else
    mid = (l+r)/2
    spawn print_number (A, l, mid) // assign to a new thread / processor
    print_number (A, mid, r)

会是 O(lgn) 吗？还是 O(n) ？

4

0 回答 0