【摘要】：时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要标志[252]。因此，算法时间复杂度通常以计算任务规模表示，并且采用计算规模表达式中最大的数量级项简化描述。假设CPU内核数为p，逻辑线程数为w，则PDDDP的每个子线程计算规模为[3M＋（T-2）×32M＋3M]/w，方法时间复杂度则为O，比串行方法显著下降，因此，算法的并行化计算理论上可随着核数的增加而大幅度提高计算效率，缩短计算时间。
时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要标志[252]。但是，算法的计算时间无法通过理论公式确切表达，需要对算法进行测试获得。因此，算法时间复杂度通常以计算任务规模表示，并且采用计算规模表达式中最大的数量级项简化描述。根据前文描述，实现DDDP并行计算的父任务规模为3M＋（T-2）×32M＋3M，因此，DDDP的复杂度为O（32M）。通过Fork/Join并行框架实现DDDP方法的并行化，父任务递归分解为多个相同的子任务，并平均分配到不同的逻辑线程中同时进行计算。目前，应用较为广泛的多核CPU根据内核数和逻辑线程数的关系分为两种：一种是逻辑线程数等于内核数；另一种则是支持“超线程”技术的配置，单个内核可以模拟出两个逻辑线程，即逻辑线程数等于内核数的两倍。由于Fork/Join并行框架是基于线程计算的并行技术，所以，计算子任务的规模与逻辑线程数有关，但是并行算法的理想时间复杂度只与内核数有关。假设CPU内核数为p，逻辑线程数为w，则PDDDP的每个子线程计算规模为[3M＋（T-2）×32M＋3M]/w，方法时间复杂度则为O（32M/p），比串行方法显著下降，因此，算法的并行化计算理论上可随着核数的增加而大幅度提高计算效率，缩短计算时间。(www.xing528.com)
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
