如何根据多个步骤计算算法的时间复杂度
如何根据多个步骤计算算法的时间复杂度
提问于 2021-03-31 22:15:55
程序的“大O”时间复杂度是多少，其中输入大小n与步数的关系是：
input size | steps
-------------------
4 | 29
6 | 175
8 | 649
10 | 1835
12 | 4334
14 | 9063
16 | 16976
18 | 29842它似乎从低于n**3开始，然后增长到比n**4需要的更少，并且似乎不是指数级的，不是吗？
回答 1
Stack Overflow用户
发布于 2021-03-31 23:18:07
TL;DR:这是不可能精确知道的，因为有无限数量的合理的解决方案。
你可以使用多项式回归来猜测复杂性的程度，假设它是多项式的，并且算法的行为是一致的(即。该算法不包含任何影响步骤数的条件结构)。
以下是原始结果( R2是描述回归质量的指标--其中R2=1表示回归接近完美)：
If the degree is 1:
Function = y(x) = 1,748.905x^1 + -11,850.452
R2 = 0.81
Mean Squared Errors: 15062257.81
Root Mean Squared Errors: 3881.012
If the degree is 2:
Function = y(x) = 207.807x^2 + -2,822.839x^1 + 8,930.202
R2 = 0.993
Mean Squared Errors: 552581.235
Root Mean Squared Errors: 743.358
If the degree is 3:
Function = y(x) = 9.997x^3 + -122.089x^2 + 436.132x^1 + -306.881
R2 = 0.999
Mean Squared Errors: 77681.188
Root Mean Squared Errors: 278.713
If the degree is 4:
Function = y(x) = -0.835x^4 + 46.721x^3 + -685.349x^2 + 3,940.647x^1 + -7,609.702
R2 = 1
Mean Squared Errors: 37326.804
Root Mean Squared Errors: 193.201
If the degree is 5:
Function = y(x) = -0.239x^5 + 12.293x^4 + -226.968x^3 + 1,992.662x^2 + -8,223.310x^1 + 12,674.167
R2 = 1
Mean Squared Errors: 4825.15
Root Mean Squared Errors: 69.463基于此，您可以放心地说，复杂性不是线性的，也不是二次的。对于其他学位，不可能说出哪一个是“正确”的。原因是1.没有足够的措施来区分可能的解，以及2. 任何数学函数都可以使用任意的高次多项式函数来逼近(有关更多信息逼近理论，请参见here )。
如果你想确定一个算法的复杂性，你需要分析代码，而不是它的黑盒行为。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66889564
复制相关文章
相似问题
腾讯云开发者
