请教一个关于算法时间复杂度的问题

[diffworld]

关于算法的时间复杂度，在大话数据结构里面有两个例子

int sum = 0, n = 100;         /* 执行 1 次 */
sum = (1 + n) * n / 2;        /* 执行第 1 次 */
sum = (1 + n) * n / 2;        /* 执行第 2 次 */
sum = (1 + n) * n / 2;        /* 执行第 3 次 */
sum = (1 + n) * n / 2;        /* 执行第 4 次 */
sum = (1 + n) * n / 2;        /* 执行第 5 次 */
sum = (1 + n) * n / 2;        /* 执行第 6 次 */
sum = (1 + n) * n / 2;        /* 执行第 7 次 */
sum = (1 + n) * n / 2;        /* 执行第 8 次 */
sum = (1 + n) * n / 2;        /* 执行第 9 次 */
printf("%d", sum);            /* 执行 1 次 */

这段代码的时间复杂度是 O(1)

而上面的这段代码还可以这样表示

int n = 10;
for(int i=0; i<n; i++)
{
    sum = (1 + 100) * 100 / 2;
}

这样修改之后代码的时间复杂度是多少？ O(1)还是 O(n)？

[kindjeff]

O(1)

[Biwood]

下面那段代码的 n 跟上面的不一样吧，如果按照下面的写法， n 为输入值，那么该算法明显是 O(n)

[ipwx]

复杂度分析是为了在理论上有个客观衡量算法优劣的指标而产生的方法，不是为了抠字眼出考题而产生的方法。

楼主你不是为了高考在学算法，是为了生产实践。这个东西你说它是 O(n) 和 O(1) 都有道理，我甚至可以认为 O(n log n) 也有道理。

（ n 在二进制机器上有 log n 长度。为了算 i++，平均复杂度为 log n ）。

与其纠结这些，楼主你还不如纠结一下为什么说快速排序的期望复杂度是 O(n log n)，最坏复杂度是 O(n^2)。

[gulucn]

循环的例子里面 sum 不是循环不变量吗？不知道编译器会不会优化成 O(1)呢？

[xialdj]

循环次数固定就是 o(1) 不固定就是 o(n)

[diffworld]

@ipwx 你好，你给的建议非常好，我是刚学数据结构的，看大话数据结构只看到第二章觉得这个地方有疑惑就提问了

[Perry]

这样出题目真的很没意思。。不过懂得人一看就是 O(1)

[lecher]

简单解释就是 O(f(n))指的是算法随数据规模的增长趋势。
f(n)就是增长函数
f(n)=1 说明输入数据的数量增加不会影响处理次数。算法的计算次数是常数级别的。
f(n)=n 说明输入数据的数量增加会导致算法的计算次数成正比增长。表现就是通常一层循环可以完成整个算法的处理，类似 2n 这种单层循环执行两次的， f(n)=2n 会省去常数项，所以也属于 f(n)=n 级别的。
f(n)=n^2 说明输入数据的数量增加会导致处理次数是成次方指数增长。通常表现就是需要两层循环嵌套处理。

想了解具体怎么算的，可以看看算法导论第一、第二章，有明确的计算方法。这个涉及高等数学的一些知识点。

[eato]

时间复杂度考虑的是以极限的方式描述算法的运行时间，一般考虑的是最坏的输入情况。像例子中的 n =100 ，可以认为 O(100)， 与 O(1) 没有多大区别。

[eato]

@eato fix: n = 10

[ghostheaven]

修改以后算法时间跟 n 有关，所以是 O(n)。修改之前算法时间跟 n 无关。

[syncher]

n = 10 的情况下， O(n) = O(10) = O(1)吧