首页 > 代码库 > 时间复杂度
时间复杂度
看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，如二分查找，如果一个for循环套一个
二分，那么时间复杂度则为O(nlogn)。
常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)
(1) for(i=1;i<=n;i++) for(j=1;j<=n;j++) s++; //n*n次，当然是O(n^2)(2) for(i=1;i<=n;i++) for(j=i;j<=n;j++) s++; //(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)(3) for(i=1;i<=n;i++) for(j=1;j<=i;j++) s++; //循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)搜索(4) i=1;k=0; while(i<=n-1){ k+=10*i; i++; //循环了n-1≈n次，所以是O(n) }(5) for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; //循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。