我真的很难理解如何确定我的程序的运行时，有一个简单的方法来做到这一点吗?此外，当我试图搜索数组中的特定元素时，为什么时间复杂度是O(1)而不是O(n)?(我认为是O(n)因为在最坏的情况下你必须遍历整个数组来找出元素是否存在)
O(n)要求您首先定义'n'可能是什么。例如，任务是:
给定数组a的整数，大小t和一个特定的整数x，返回x所在的第一个索引出现在a;如果x返回-1不在a中.
然后，我想到了这个算法:
for (int i = 0; i < a.length; i++) if (a[i] == x) return i;
return -1;
该算法为O(t)。
那是什么意思?
好，画个图。在x轴上，输入"花费的时间"(或占用的内存;您可以根据需要测量空间复杂性或时间复杂性)。在y轴上，输入't':数组的大小。
现在开始运行你的算法。首先是1个大小的数组，然后是2个大小的数组，然后继续。最终形成一个百万大小的数组。画出来
在0点附近(小数组)到处都是。wildswing—您更多地测量JVM启动时间，您的音乐播放器是否正在切换到下一个曲目，您的浏览器是否正在执行一些工作，谁知道呢。真是一团糟。但最终这条线会稳定下来。一旦你的输入数组中有几百万个项目，热点启动，VM预热，音乐播放器-这些都不再对测量产生有意义的影响。
一旦线稳定下来，它看起来像什么?
一个O(n)算法说:"它看起来像一条非水平的直线"。因为如果你画出y = C*x(为C选择任意常数)，它看起来像一条非水平直线。
O(1)算法看起来像一条水平线(为什么?因为y = C看起来是那样的)。O(n^2)算法看起来就像y = x^2，如果你把它画出来，依此类推。就像y = 812398x^2 + 234124124x最终看起来几乎完全像y = x^2一样，只要你"足够向右"，在O(x)符号中，常数因子和重叠因子(812398是常数，234124124x部分是重叠的)被忽略了。这是关于"图形最终是什么样子的?"’，而这些方面根本不影响这一点。
现在你知道O(n)的意思了。那么解释为什么这个算法是O(n)就很简单了:如果你的数组中有一百万个数字，你必须检查一百万个条目才能找出答案。无论谁告诉你这是O(1)都是错误的，或者更有可能是你听错了。也许他们在谈论:
这有多难，给定一些优化的集合来完成这个任务，以确定给定的整数x是否在数据结构a中，其中有t元素。
对于数组，答案是O(n)，但如果a是HashSet，答案是O(1)。哈希集不需要检查每个元素。
在数组中搜索0 (n)次。就像这样，如果你的数组中有n个元素，你要找的元素有可能在数组的末尾。所以你需要检查每个元素，我们称之为动作。因为有n个元素，所以有n个动作，因此有O(n)。