为什么将方阵乘法的时间复杂度定义为O(n ^ 3)? [英] why is the time complexity of square matrix multiplication defined as O(n^3)?

问题描述

我在多个来源(在线和书籍)中都遇到过-对于大小为nXn的矩阵，平方矩阵乘法的运行时间为O(n ^ 3). (例如-矩阵乘法算法的时间复杂度)

I have come across this in multiple sources (online and books) - Running time of square matrix multiplication is O(n^3) for matrices of size nXn. (example - matrix multiplication algorithm time complexity)

此语句将表明此乘法过程的运行时间上限为C.n ^ 3，其中C为某个常数，而n> n0，其中n0为某些输入，超出该上限即成立. ( http://en.wikipedia.org/wiki/Big_O_notation 和Θ(n)和O(n)有什么区别?) 问题是，我似乎无法导出常数C和n0的值.

This statement would indicate that the upper bound on running time of this multiplication process is C.n^3 where C is some constant and n>n0 where n0 is some input beyond which this upper bound holds true. (http://en.wikipedia.org/wiki/Big_O_notation and What is the difference between Θ(n) and O(n)?) Problem is, i cannot seem to derive the values of constants C and n0.

我的问题-

1. 有人可以为方矩阵乘法的大哦是O(n ^ 3)"的陈述提供数学证明吗?

1. Can someone provide a mathematical proof for the statement 'big Oh of square matrix multiplication is O(n^3)' ?

C和n0的值是多少?

what are the values of C and n0 ?

推荐答案

1. 彼此之间有3个for循环，每个循环从0到n-1(或1到n)(可以看到在您提供的链接中，即使它不是完全正确的)，也会导致O(n ³ ).将其形式化为适当的证明应该很容易.

1. There are 3 for loops within each other going from 0 to n-1 (or 1 to n) each (as can be seen in the link you provided, even though it's not completely correct), this results in O(n³). Formalizing it into a proper proof should be easy enough.

a)为了得到正式的证明，需要根据某些操作集(通常是任何算术操作)来定义运行时间.在3个for循环中，有2个算术运算(1个乘法，1个加法)，因此我们得到2.n3，因此C = 2.

a) For a formal proof, running time needs to be defined in terms of some set of operations, commonly taken to be any arithmetic operation. Inside the 3 for loops there are 2 arithmetic operations (1 multiplication, 1 addition), thus we get 2.n3, thus C = 2.

b)n0 = 0，因为从n = 1开始成立

b) n0 = 0 because this holds true from n = 1

请注意，由于big-O只是一个上限，我们还可以说，对于任何k> = 3而言，该算法的复杂度为O(n ^k )(如果使用big-Theta表示法，则为true).我们还可以将C和n0分别设为大于2和0的任何值(因为不需要找到最小的可能值).

Note that, since big-O is just an upper bound, we can also say the complexity of this algorithm is O(n^k) for any k >= 3 (the same would not be true if we use big-Theta notation). We can also take C and n0 to be any value greater than 2 and 0 respectively (since the requirement isn't to find the smallest possible values).

这篇关于为什么将方阵乘法的时间复杂度定义为O(n ^ 3)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！