2 tidusnake tidusnake 于 2016.03.24 10:27 提问

一个关于时间复杂度问题
 for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
    // do something
    }
}

这种我不太清楚,外层循环是n,但是内循环次数是1到n,所以这种算是O(n^2)吗。谢谢

5个回答

qq423399099
qq423399099   Ds   Rxr 2016.03.24 10:38
已采纳

一共执行了(1+2+3+...+n-1+n)≈(n^2)/2,因为时间复杂度是不考虑系数的,所以时间复杂度也是O(n^2)

sl_18500
sl_18500   2016.03.24 10:35

当n=5时
i:0 1 2 3 4 5

j: 0 0,1 0,1,2 0,1,2,3 0,1,2,3,4

fickyou
fickyou   2016.03.24 10:39

对,就是O(n^2)

huixion
huixion   2016.03.24 10:39

算O(n^2)吧,1+2+3+4+5+.......+n=n*(n+1)/2

enpterexpress
enpterexpress   Rxr 2016.03.24 10:57

O(n^2)

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
算法基础(二)——算法时间复杂度和渐进时间复杂度 .
算法时间复杂度的本质是算法的执行时间,也就是算法中所有语句的频度之和。上一篇博客中说了,语句频度就是语句的执行次数,它与算法求解问题的规模大小息息相关。     假设对于给定的算法,目前问题规模为n,则语句频度可以表示成一个关于问题规模的函数 T(n),那么算法时间复杂度也就可以用T(n)表示,其含义是算法在输入规模为n时的运行时间。     当问题规模很大时,精确的计算T(n)是很难实现而且
关于算法时间复杂度的计算
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
用分治法求最大子序列问题,时间复杂度O(N*logN)
package Test; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class MaxSubSequenceSum { public static void main(String[] args) throws IOExcept
算法复杂度函数级T(n)非O(n)分析
定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时
动态规划时间复杂度
一、一维动态规划问题    一维动态规划时间复杂度一般有O(n)和O(n^2)两种,时间复杂度取决于状态转移方程。    1.如果第i个状态的确定需要利用前i-1个状态,即dp[i]由dp[i-1],dp[i-2],...,dp[0]决定,那么此时的时间复杂度为O(n^2)。如 leetcode139.单词拆分:139. 单词拆分给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDic...
关于时间复杂度的几个典型证明
0x01 证明O(f)+O(g)=O(f+g)O(f)+O(g)=O(f+g)O(f)+O(g) = O(f+g) 令F(n)=O(f)F(n)=O(f)F(n)=O(f),则存在自然数n1n1n_1、正数c1c1c_1,使得任意自然数n≥n1n≥n1n\geq n_1,有: F(n)≤c1f(n)F(n)≤c1f(n)F(n)\leq c_1f(n) 同理,令G(n)=O(g)G(n)...
算法的复杂度——算法的时间复杂度和空间复杂度
在一次笔试题目中,发现了自己对于算法的时间复杂度问题上并没有完全清晰这个概念和计算方法,故上网寻找到比较好的详细介绍来学习。 算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少
约瑟夫问题,从o(n*m)到o(n)乃至o(m)的算法复杂度进阶
约瑟夫问题,从o(n*m)到o(n)乃至o(m)的算法复杂度进阶
关于递归的误区
一个算法的实现,关于在递归时间复杂度上的考证
算法导论-最大子数组问题-线性时间复杂度算法分析与实现
之前写了最大子数组问题的分治法,今天把这个问题的线性时间复杂度的算法写出来。 这个方法在算法导论最大子数组问题的课后思考题里面提出来了,只是说的不够详细。 思考题如下:使用如下思想为最大子数组问题设计一个非递归的,线性时间复杂度的算法。从数组左边界开始,由左至右处理,纪录到目前为止已经处理过的最大子数组。若已知A[1...j]的最大子数组,基于如下性质将解扩展为A[1...j+1]的最大子数组