关于循环展开的时间复杂度
  • 板块学术版
  • 楼主FurippuWRY
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/12/3 13:16
  • 上次更新2023/12/3 15:33:30
查看原帖
关于循环展开的时间复杂度
993779
FurippuWRY楼主2023/12/3 13:16

如果有一个循环

long long ans = 0, n = 1e9;
for (long long i = 1; i <= n; ++i) {
    ans += i;
}

改写为

long long ans = 0, n = 1e9;
for (long long i = 1; i <= n; i += 5) {
    ans += i;
    ans += (i + 1);
    ans += (i + 2);
    ans += (i + 3);
    ans += (i + 4);
}

那么循环展开时间复杂度是 O(n)O(n) 还是 O(n5)O(\dfrac{n}{5})?

2023/12/3 13:16
加载中...