分析跨度 - 两个并行的

Question

如果我有两个并行的算法，我想分析算法的跨度，我该怎么做？

例如

parallel for a=2 to n 
    parallel for b=1 to a-1 

我的猜测是跨度THETA（LG（N）* LG（N）），但我不知道。 :)有人谁可以帮助或提示？

Answer 1

我假设你想要这个算法的time complexity。由于时间复杂度并不是算法实际需要多少时间，而是需要多少操作[支持这种说法的报价如下]，因此该算法的时间复杂度为O(n^2)，因为它是不平行的。

从wiki页面：Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform

我们为什么不关心事实的算法是并行？
通常，我们的簇大小是固定的，并且不依赖于输入[n]。我们可以同时执行k操作，并且算法是O(n^2) [为了简化假设正好n^2]
假设我们有一个大小为100的输入，那么它将'取'(100^2)/k时间。如果大小为1,000，则需要(1000^2)/k，对于n个元素：(n^2)/k，如您所见，k是一个常数，并且程序并行的事实不会改变复杂性。能够一次完成k的操作，并不是更好[甚至是值得的，但这是另一个线程]，然后计算机时间更快。