算法 时间复杂度概念及案例
大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说算法 时间复杂度概念及案例,希望能够帮助大家进步!!!
概念
常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分，如果记为f(N)，那么时间复杂度为O(f(N))。
算法的时间复杂度，用来度量算法的运行时间，记作: O(f(N))。它表示随着 输入大小N的增大，算法执行需要的时间的增长速度可以用 f(N) 来描述。
上面概念可能比较抽象，下面我们用案例的方式来举例下,一般我们是先拿到f(N)，然后来算下他的时间复杂度，一般我们只保留对函数增长速度较大的函数
例如:
1、f(N)=c（c是常数），我们称时间复杂度为O(1)
2、f(N)=a*N+b(a和b是常数)，我们称时间复杂度为O(N)
3、f(N)=a*N^2+b*N+c(a,b,c均为常数)，我们称时间复杂度为O(N^2)
4、f(N)=a*N^2*logN+b*N+c(a,b,c均为常数)，我们称时间复杂度为O(N^2*logN)
案例
public String test() {
System.out.println("hello world"); // 需要执行 1 次
return "你好"; // 需要执行 1 次
}只听到从架构师办公室传来架构君的声音:
污莱一棱水周围，岁岁蜗庐没半扉。有谁来对上联或下联?
上面的代码执行了2次，则f(N)=2;则时间复杂度为O(1);
public int test() {
for (int i = 0; i < N; i++) {
System.out.println("hello world1"); // 需要执行 N 次
System.out.println("hello world2"); // 需要执行 N 次
}
System.out.println("hello world3"); // 需要执行 1 次
}上面的代码执行了2N+1次，则f(N)=2N+1,时间复杂度为O(N)
public int test() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println("hello world"); // 需要执行 N*N 次
}
}
}上面的代码执行了N*N次，则f(N)=N^2，时间复杂度为O(N^2)
当出现条件或者顺序执行的语句时，总是取最大的时间复杂度,或者说最差的情况
public int test() {
//循环1：时间复杂度为O(N^2)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println("hello world"); // 需要执行 N*N 次
}
}
//循环2：时间复杂度为O(N)
for (int i = 0; i < N; i++) {
System.out.println("hello world1"); // 需要执行 N 次
}
}上面代码的时间复杂度为O(N^2+N)=O(N^2)
public int test() {
if(){
//循环1：时间复杂度为O(N^2)
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.println("hello world"); // 需要执行 N*N 次
}
}
}else{
//循环2：时间复杂度为O(N)
for (int i = 0; i < N; i++) {
System.out.println("hello world1"); // 需要执行 N 次
}
}
}上面代码的时间复杂度为O(N^2)
腾讯云开发者
