Question

算法分析中O（n）什么含义

我知道这是时间复杂度，我想知道O（n）是高阶无穷小的意思吗？是不是说O(n)/o的极限是零呢？请解释一下： for(i=0;i<n;i++) for(j=0;j<n;j++) { c[i][j]=0; for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; }共n3次乘法、n3次加法时间复杂度为O(n3) 为什么时间复杂度是O(n3)，请解释

Answer 1

O(n)这个大O表示的是最坏情况下的时间复杂度，就比如你举的例子，一共n^3次乘法和n^3次加法，那么加起来就是2×n^3。 然后如果有一个表达式f(n)，使得n趋于无穷大的时候，lim(2×n^3)/f(n)=常数c，那么就可以用大O表示。表示为O(f(n))，而且规定f(n)的表达式是不带常数的系数的，那么在这里f(n)=n^3。 一般用大O表示算法复杂度只需要取次数最高的项，而且去掉系数就OK了，不用每次都这么算的。三重循环而且每重循环都执行n次的话直接O(n^3)就好了。

Answer 2

O（n） 表示运行时间的上界 通俗点说就是算法运行的最坏情况该程序有三重循环 由c[i][j]=c[i][j]+a[i][k]*b[k][j];可知进行一次乘法必进行一次加法 故T（n)<=n^3+n^3=2n^3=cn^3故T（n）=O（g（n））=O（n^3)