我一直认为:
1 + 2 + 3 + ... + n 是O(n),将两个n×n矩阵相加就是O(n ^ 2)。
1 + 2 + 3 + ... + n
但是今天我从一本教科书中读到,“通过前n个整数之和的公式,这是n(n + 1)/ 2”,然后是:(1/2)n ^ 2 +(1/2) n,因此为O(n ^ 2)。
我在这里想念什么?
在大O表示法可用于确定增长率的任何功能。
在这种情况下,这本书似乎不是在谈论计算价值的时间复杂性,而是价值本身。和n(n+1)/2是O(n^2)。
n(n+1)/2
O(n^2)
我在Karumanchi教科书中读到1 + 2 + 3 + ... + k = k(k + 1)/ 2> n => k = O(√n)。这是怎么发生的。你能给我解释一下吗...谢谢