请问我的为什么会超时呢？是因为用了函数吗？

more_Power @ 2023-09-05 15:28:06

#include<iostream>
using namespace std;

double Sn(int x)
{
    double sn = 0;
    for (int i = 1; i <= x; i++)
        sn += 1.0 / i;
    return sn;
}
int main()
{
    int k;
    cin >> k;
    long i;
    for (i = 1; Sn(i) <= k; i++)
    {
    }
    cout << i;
    system("pause");
    return 0;
}

by FurippuWRY @ 2023-09-05 15:35:13

@KNNNNNN
首先 没必要一篇帖子发三遍
第二 《system("pause");》

by Withershine @ 2023-09-05 16:04:25

system("pause");

不会导致超时吧

by VIOLET__FOREVER @ 2023-09-05 16:07:47

@KNNNNNN 去掉 system("pause"); 不能解决问题，代码本身就存在超时风险，可以利用类似记忆化优化，就是原来的计算过的内容不必要重复计算，函数可以小改一下。求关

by more_Power @ 2023-09-05 16:08:04

@FurippuWRY 啊我竟然发出去了！我还以为没发成功，连续点了好多下都是发布erro就没管了

我把函数去掉之后融到单纯的for循环之后就过了，我感觉问题是出在函数上，但具体不知道是为什么，是因为函数处理时间过长？

关于第二点，

system("pause");

是我在网上学的为了程序运行完停留显示结果的一个语句，之前用的时候都没超时，为什么这次超时了呢？ 求解答

by VIOLET__FOREVER @ 2023-09-05 16:14:38

@KNNNNNN 看看我上面的，我觉得是算多次了，就是 1,2,3... 这些数一直被重复计算导致时间复杂度直接上去了

by more_Power @ 2023-09-05 16:42:47

@VIOLET__FOREVER 嘶……我咋看不出来啥重复计算了呢？可以说得详细一点吗

我感觉就是循环控制变量传参过去调用函数然后和k比大小，怎么就重复计算了呢？

by VIOLET__FOREVER @ 2023-09-05 16:54:54

@KNNNNNN 我觉得是每次调用函数的时候都是从 1 开始算的，就相当于是 1 会被计算很多次,就像是我 2 的时候明明已经算出了 \frac{1}{1}+\frac{1}{2} 但是按照你的算法到 3 的时候就算了 \frac{1}{1}+\frac{1}{2}+\frac{1}{3} 就相当于是把 \frac{1}{1}+\frac{1}{2} 重复计算了，我觉得可以拿一个变量把前面算过的存起来，然后每一次加一个 \frac{1}{n} 就行了，这样就可以变成线性了

by Darling_ZX @ 2023-09-05 17:00:51

@KNNNNNN 按你的程序来跑最大值k=15 很明显n=1835421,你的复杂度就会是 \sum (1835421) 很明显过不去一秒

by Darling_ZX @ 2023-09-05 17:02:43

@KNNNNNN 说白一点，你可以记录每一次累加的值为sum，枚举i的时候就可以直接加上1/n,复杂度就正确了，为线性

by Darling_ZX @ 2023-09-05 17:04:55

@KNNNNNN 如下给出部分

double sum=1;
cin>>k;
while(sum<=k){
    n++;
    sum += 1.0/n;
}