Tae*_*ahn 5 performance big-o time-complexity
所以,假设你有一个功能,X(N)那就是一个完整的黑盒子.你不知道函数的增长率,你不能查找,你不能查看源(目前).
接下来让我们在另一个函数的上下文中检查它
for(int i = 0; i < N; ++i)
X(N);
你写的代码是线性的,但显然该函数X具有的增长速度的冲击你的功能.例如,如果X(N)扩展到for(int i = 0; i < N; ++i)您的函数是二次的.
我的问题是:如果有人问你的功能大O是什么,描述你的功能增长率的最佳方法是什么？
我说我会称之为线性,我的答案的辩护如下.
如果您知道实际增长率X,则可以准确估计代码,但尽管您可以(以某种方式)最终获得代码,但大多数函数都没有提供性能统计信息.
因此,如果您确实可以访问代码X,您可以将其包含在您的估算中,但是您在哪里划线？X可能还会调用其他函数,然后调用其他函数.我觉得在制造场景之外,你处理的是完美划分的代码,如果你还不知道调用黑盒函数的增长率,你必须决定估计你可以使用的代码.
如果你谈论画线,我只想提供如下: -
代码的复杂性: - O(N*o(X))
一旦得到判断函数X(N)的复杂性,就可以简单地用公式代替.
到那时,它将是一个简写但有用的符号,同时满足循环的复杂性.