java在给出这个时间表的情况下，我如何判断时间复杂度？

# 1 楼答案

它有助于理解O(n)实际上是什么意思。要将其可视化，请制作一个简单的折线图。把n放在X轴上，不管n是什么，然后把你测量的复杂度放在Y轴上。目标通常是“时间复杂度”，因此，CPU通过计算给定“n”值的输入集所需的时间

如果你真的做了这个实验，对于低“n”，图表只是随意结果的一点点乱七八糟；运气是控制因素，因此，你无法做出正面或反面的判断（在那一次测试中，你的winamp切换歌曲，在这一次测试中，ArrayList开始时的容量为10，这意味着在11时，你会看到一个突然的峰值，等等）

但是，继续。最终，你不知道这需要多长时间，但最终，一个形状开始成形。要么是因为你缩小得足够远（因为你的图形非常大，从n=1到n=100000），要么是因为算法的复杂性“占据了主导地位”，是控制因素

这就是O（n）所衡量的：一旦这个图形看起来稳定下来，它的形状会是什么样子？如果你说一个算法是O(n log n)，你是说：图的右边看起来很像图的右边y = x * log(x)

这也是为什么O(n^2 + n)不是一件事的原因——如果你画y = x^2 + x，一旦你走到右边，它看起来会和y = x^2完全一样。考虑到问题的关键是“形状是什么”，一旦你走得足够远，任何对形状没有意义影响的因素都是无关紧要的

这为你提供了一个非常强大的工具来回答这些问题。拿出一支笔。拿出一些纸来。疯狂地画这个。认真地说，拿出一支笔来做：画一条线，在x轴上画10个记号，突出显示第一、第二、第五和第十个（n=100、n=200、n=500、n=1000）。然后，从~0-500绘制一个y轴，并在x=100，y=33处绘制一个点。同样在x=200，y=76，等等。尽最大努力画出这条“趋势线”。然后拿出你的图形计算器或者去wolfram alpha打印^{}的图形