大O，将一系列n个数相加的复杂度是多少? [英] Big O, what is the complexity of summing a series of n numbers?

问题描述

我一直以为它的复杂性:

1 + 2 + 3 + ... + n为O(n)，将两个n×n矩阵相加将为O(n ^ 2).

但是今天我从一本教科书中读到，根据前n个整数之和的公式，这是n(n + 1)/2"，然后是:(1/2)n ^ 2 +(1 /2)n，因此就是O(n ^ 2).

我在这里想念什么?

解决方案

大O符号可以用来确定 any 函数的增长率.

在这种情况下，这本书似乎不是在谈论计算价值的时间复杂性，而是价值本身.而n(n+1)/2是O(n^2).

I always thought the complexity of:

1 + 2 + 3 + ... + n is O(n), and summing two n by n matrices would be O(n^2).

But today I read from a textbook, "by the formula for the sum of the first n integers, this is n(n+1)/2" and then thus: (1/2)n^2 + (1/2)n, and thus O(n^2).

What am I missing here?

解决方案

The big O notation can be used to determine the growth rate of any function.

In this case, it seems the book is not talking about the time complexity of computing the value, but about the value itself. And n(n+1)/2 is O(n^2).

这篇关于大O，将一系列n个数相加的复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！