时间&空间复杂度

1.时间复杂度

定义：时间复杂度是一个函数，定量描述该算法运行时间。算法中基本操作的执行次数，为算法的时间复杂度。

推导大O阶的方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

例题1：

void func1(int N){int count = 0;for (int i = 0; i < N ; i++) {for (int j = 0; j < N ; j++) {count++;}}for (int k = 0; k < 2 * N ; k++) {count++;}int M = 10;while ((M--) > 0) {count++;

当外层循环i=0时，内层循环执行N次，i=2时，内层循环执行N次…….,当i=n,内层循环执行N次。所以，该算法执行次数为N^2+2N+10；

根据推导大O阶的方法1，去掉10，根据推导大O阶的方法2，去掉2N，最终得到该算法的时间复杂度为O（N^2）

在实际情况中，关注的是算法最坏运行情况

例题2：

// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

假设N=5：算法最坏运行情况是树每个节点都有值，满的时候，即2^N-1.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vLkvogpj-1635388739886)(E:\2022大四春招冲刺\笔记\1635322834194.png)]

根据大O阶方法算出时间复杂度为O（2^n）

2.空间复杂度

定义：算法在运行过程中临时占用存储空间大小的量度。空间复杂度算的是变量的个数。

例题1：

void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}

随着N变大，变量不会变多，只有一个变量sorted,所以空间复杂度为O（1）

例题2：

int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}
return fibArray; }

当N越来越大时，数组中存的值会越来越多，变量变多，所以是O（n）

练习

1. 给定整型数组, 把所有的偶数放到数组前面, 把所有奇数放到数组后面.

2. 给定两个整型数组, 交换两个数组的内容.

数据类型+运算符

1.变量和类型

1.1整形变量

int占4个 字节

什么是字节：字节是计算机表示空间大小的基本单位，计算机使用二进制表示数据，8个二进制位bit为一个字节byte.

1KB = 1024 Byte, 1MB = 1024 KB, 1GB = 1024 MB.

System.out.println(Integer.MAX_VALUE);  // int 的最大值
System.out.println(Integer.MIN_VALUE);  // int 的最小值
//范围在 -2^31 -> 2^31-1之间

1.2长整型变量

long占8个字节

注意事项:

1.基本语法格式和创建 int 变量基本一致, 只是把类型修改成 long

2.使用 10 初始化也可以, 10 的类型是 int, 10L 的类型是 long, 使用 10 L 或者 10 l 更好一些.

long num = 10L; // 定义一个长整型变量
System.out.println(num) ;//表示的数据范围 -2^63 -> 2^63-1
System.out.println(Long.MAX_VALUE);
System.out.println(Long.MIN_VALUE) 
// 运行结果
9223372036854775807
-9223372036854775808

1.3双精度浮点变量

double占8个字节

可以用来表示小数

1.4单精度浮点型变量

float占4字节

可以用来表示小数，但是一般推荐使用double

float num = 1.0f;    // 写作 1.0F 也可以
System.out.println(num);

1.5字符类型变量

char占两个字节

1.6字节类型变量

byte为一个字节

short占2个字节

1.7 Boolean类型

1. boolean 类型的变量只有两种取值, true 表示真, false 表示假.

2. Java 的 boolean 类型和 int 不能相互转换, 不存在 1 表示 true, 0 表示 false 这样的用法.

3. boolean 类型有些 JVM 的实现是占 1 个字节, 有些是占 1 个比特位, 这个没有明确规定

1.8字符串类型变量

注意事项:

1. Java 使用 双引号 + 若干字符 的方式表示字符串字面值.

2. 和上面的类型不同, String 不是基本类型, 而是引用类型(后面重点解释).

3. 字符串中的一些特定的不太方便直接表示的字符需要进行转义.

转义字符示例:

// 创建一个字符串 My name is "张三" 
String name = "My name is \"张三\"";

1.9变量命名规则

硬性指标:

1. 一个变量名只能包含数字, 字母, 下划线

2. 数字不能开头.

3. 变量名是大小写敏感的. 即 num 和 Num 是两个不同的变量.

注意: 虽然语法上也允许使用中文/美元符($)命名变量, 但是 强烈 不推荐这样做.

软性指标

1. 变量命名要具有描述性, 见名知意.

2. 变量名不宜使用拼音(但是不绝对).

3. 变量名的词性推荐使用名词.

4. 变量命名推荐 小驼峰命名法, 当一个变量名由多个单词构成的时候, 除了第一个单词之外, 其他单词首字母都大

**小驼峰命名法**
int maxValue = 100; 
String studentName = "张三";

1.10常量

final修饰的常量，只能赋值一次。不能修改常量值。

final int a = 10; 
a = 20; // 编译出错. 提示 无法为最终变量a分配值

1.11数据类型转换

int a=10;
long b=a;//显示类型转换
long l=11;
//a=l;l是8个字节，a是4个字节，这里编译错误
a=(int)l;//强制类型转换

1.12数值提升

例题1：

int a=10;
long b=20;
int c=a+b;//相当于int=long,编译出错//当 int 和 long 混合运算的时候, int 会提升成 long, 得到的结果仍然是 long 类型。

例题2：

byte a=1;
byte b=2;
byte c=a+b;//byte=int
//修改为：byte c=byte（a+b）
System.out.print(c);//编译错误
//因为a和b都是1个字节，计算机在处理小于一个字节的运算时，会全部提升为4个字节（整型）在运算

例题3：

byte d=1+2;//byte d=3;
System.out.print(d);//正确执行

例题2中```byte c=a+b;` ``a+b是变量，例题3中1+2是常量。

变量：是在程序运行的时候，才去取数据。

常量：是在程序编译的时候，就知道这个值是几了

1.13int和string之间转换

int—->string

int num = 10; 
// 方法1 
String str1 = num + ""; 
// 方法2 
String str2 = String.valueOf(num);
//valueOf()返回int参数的字符串int形式

string—>int

String str = "100"; 
int num = Integer.parseInt(str);

2.运算符

2.1算数运算符

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UrCY98ik-1635388739890)(C:\Users\86139\AppData\Roaming\Typora\typora-user-images\1635382346478.png)]

2.2关系运算符

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tCXWmqok-1635388739892)(E:\2022大四春招冲刺\笔记\1)]

2.3位运算符

& | ^ ~ 位运算符：针对2进制位

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P1DmVRis-1635388739893)(E:\2022大四春招冲刺\2)]

往左移，右边补0，往右移，左边补符号位(正数补0, 负数补1)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MEn3EAWE-1635388739894)(E:\2022大四春招冲刺\3)]

三目运算符：表达式1？表达式2：表达式3

如果表达式1为true，执行表达式2，否则执行表达式3.

逻辑控制

1.Switch

注：switch一定要有break

不能做Switch的参数类型：float,double,long,boolean

能做参数的特殊类型：枚举，字符串。

2.3位运算符

& | ^ ~ 位运算符：针对2进制位

[外链图片转存中…(img-P1DmVRis-1635388739893)]

往左移，右边补0，往右移，左边补符号位(正数补0, 负数补1)。

[外链图片转存中…(img-MEn3EAWE-1635388739894)]

三目运算符：表达式1？表达式2：表达式3

如果表达式1为true，执行表达式2，否则执行表达式3.

逻辑控制

1.Switch

注：switch一定要有break

不能做Switch的参数类型：float,double,long,boolean

能做参数的特殊类型：枚举，字符串。