C++ 计算Collatz序列长度和的优化算法

问题描述:

给定一个范围 [m, n]，计算该范围内所有整数的Collatz序列长度和。

原算法:

#include <iostream>
using namespace std;

int main()
{
    int T;
    cin >> T;
    int *p;
    p=new int[T];
int j=0;
    for (int h = 0; h < T; h++)
    {
        int m, n, sum;
        cin >> m >> n;
        sum = n - m + 1;
        for (int i = m; i <= n; i++)
        {
            int k = i;
            while (k != 1)
            {
                k = (k % 2 == 0) ? k >> 1 : 3 * k + 1;
                sum++;
            }
        }
        p[j]=sum;
        j++;
    }

for(int i=0;i<T;i++)
{
  cout<<p[i]<<endl;
}
    return 0;
}

优化算法:

#include <iostream>
using namespace std;

int collatzLength(int n) {
    int length = 1;
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3 * n + 1;
        }
        length++;
    }
    return length;
}

int main() {
    int T;
    cin >> T;
    int *p = new int[T];
    for (int h = 0; h < T; h++) {
        int m, n, sum = 0;
        cin >> m >> n;
        for (int i = m; i <= n; i++) {
            sum += collatzLength(i);
        }
        p[h] = sum;
    }

    for (int i = 0; i < T; i++) {
        cout << p[i] << endl;
    }

    delete[] p;
    return 0;
}

优化思路:

函数化: 将计算单个整数Collatz序列长度的功能封装到collatzLength函数中，避免重复计算。
循环遍历: 使用循环遍历范围内的所有整数，并将每个整数的Collatz序列长度累加到sum变量中。

时间复杂度分析:

原算法时间复杂度为 O(n^2)，其中 n 为范围大小。优化算法时间复杂度为 O((n-m+1)logn)，因为每个整数的Collatz序列长度平均为 O(logn)。

结论:

优化算法通过函数化和循环遍历，避免了重复计算，提高了算法的效率，时间复杂度也显著降低。