一个容易的多线程算法的时间复杂度分析例子
一个简单的多线程算法的时间复杂度分析例子
小弟最近看《算法导论》里关于多线程算法的部分内容，里面提到一个并行运算的for循环，如下：
很简单吧，然后说时间复杂度是O(lgn),原文是说span为O(lgn)，意思差不多吧？
我就纳闷了，既然并行，为什么不是O(1)的时间复杂度呢，在常数时间内，所有y[i]就可以同时赋值完成吧？
难道是我理解错了作者的意思，看的英文版电子书、、、、作者的解释理解不能，说“because the recursive spawning dominates the constant time work of each iteration.”
真心求教，这个不懂影响后面很多其他多线程算法的分析，跪求大牛指点啊！
------解决方案--------------------
创建一个线程是O(1)。创建n个线程是多少？书上的意思是创建n个线程可以O(logn)解决。创建完n个线程以后当然是O(1)，但是创建线程本身也有开销的。
小弟最近看《算法导论》里关于多线程算法的部分内容，里面提到一个并行运算的for循环，如下：
parallel for i = 1 to n
y[i] = 0;
很简单吧，然后说时间复杂度是O(lgn),原文是说span为O(lgn)，意思差不多吧？
我就纳闷了，既然并行，为什么不是O(1)的时间复杂度呢，在常数时间内，所有y[i]就可以同时赋值完成吧？
难道是我理解错了作者的意思，看的英文版电子书、、、、作者的解释理解不能，说“because the recursive spawning dominates the constant time work of each iteration.”
真心求教，这个不懂影响后面很多其他多线程算法的分析，跪求大牛指点啊！
------解决方案--------------------
创建一个线程是O(1)。创建n个线程是多少？书上的意思是创建n个线程可以O(logn)解决。创建完n个线程以后当然是O(1)，但是创建线程本身也有开销的。