我一直在努力理解就是最好的可能运行时间：大欧米茄分析
for t = 1 to n
sum = 0
for i = 1 to t
sum = sum + x[i]
据我所知，第一个循环会n次。这是我与之斗争的内部循环。 内部循环将在第一次进入n（n + 1）/ 2，但下一次将进入n（n + 1）/ 2 -1。 我不确定如何将此转换为最佳运行时间。
如果可能，我可以在正确的方向上使用推送。 谢谢！
为了形象化这个，我拿想象充满了正方形或弥漫着骰子体积区域的方法更复杂的情况。每个方块代表一个原子步骤。外循环迭代的所有步骤放在同一行上。对于你来说，它看起来像这样：
t=1 #
t=2 ##
t=3 ###
t=4 ####
t=5 #####
正如你所看到的，这些形成一个三角形，谁的高度为N和谁的宽度也N.如果你现在算平方（N *（N + 1 ）/ 2）你有内循环的迭代次数。乘以该项并删除不相关的术语会带来复杂性Θ（N * N）。
您为分析O（n）的尝试增加了一点复杂性。这可能是你为什么感到困惑的原因。
我们知道外环for 1到t是线性的。内部循环随着时间的推移运行更多。在t = 1时，它运行一次，在t = n时，它运行n次。
我们运行for循环的平均次数是多少？
avg = (1 + n)/2
这是你发现了，虽然你试图来遍历它的价值。我们所需要的是我们计算的平均值。
因为1对n的高值n相对不重要，所以我们可以近似为n/2。
所以外循环运行n次。内部循环运行n/2次。
n * n/2 = 0.5n^2
因为我们通常会忽略最乘值，我们可以说，O(n) = n^2
请详细说明---这里的“t”是什么（t的值）？另外，我想你需要更严格的分析！ – 2014-09-19 20:49:59