如何将鱼群增长计算代码从O(N²)优化为O(N)解决256天模拟运行超时问题

原代码性能问题分析 #

• 原实现直接存储每条鱼的剩余繁殖倒计时，每天遍历全量鱼群更新状态，随着天数增加鱼群数量指数级暴涨，实际时间复杂度是指数级，远高于O(N²)，256天模拟完全无法运行
• 递归调用也会带来额外的栈开销，虽然不是核心问题但也属于可优化项

优化思路（时间复杂度O(1)，远优于要求的O(N)） #

不需要逐个存储单条鱼的状态，改为统计剩余繁殖天数为k的鱼的总数量即可，鱼的倒计时取值范围固定为0~8，仅需一个长度为9的计数数组就能完成全部模拟：

1. 初始化时统计输入中每个剩余天数对应的鱼的数量，存入计数数组
2. 每天按如下规则更新计数：
   • 取出剩余天数为0的鱼的数量，这就是当天新繁殖的鱼的数量
   • 所有剩余天数≥1的鱼的计数整体左移一位（即剩余天数为i的鱼的数量赋值给剩余天数为i-1的位置）
   • 当天完成繁殖的鱼重置为6天倒计时，将对应数量加到剩余天数为6的计数上
   • 新出生的鱼初始为8天倒计时，将繁殖数量赋值给剩余天数为8的计数
3. 模拟完256天后，将计数数组所有值求和就是总鱼群数量

优化后代码 #

#include <fstream>
#include <vector>
#include <iostream>
#include <numeric>

int main() {
    std::ifstream myfile("inputday6.txt");
    int a;
    // 计数数组下标代表剩余繁殖天数，值为对应鱼的数量
    std::vector<int64_t> count(9, 0);
    while (myfile >> a) {
        count[a]++;
    }
    myfile.close();

    for (int day = 0; day < 256; ++day) {
        int64_t new_fish = count[0];
        // 所有鱼倒计时减1
        for (int i = 0; i < 8; ++i) {
            count[i] = count[i + 1];
        }
        // 繁殖过的鱼重置为6天倒计时
        count[6] += new_fish;
        // 新出生的鱼初始为8天倒计时
        count[8] = new_fish;
    }

    int64_t total = std::accumulate(count.begin(), count.end(), 0LL);
    std::cout << "Day 256: " << total << std::endl;
    return 0;
}

优化效果说明 #

不管初始鱼群数量多大，模拟过程只需要遍历固定长度为9的数组，256天总运算量只有256*9=2304次，运行耗时可以忽略，同时避免了存储指数级增长的鱼群数据，内存占用也稳定在极低水平。

内容的提问来源于stack exchange，提问作者Jojo