软件编程
位置：首页>> 软件编程>> java编程>> Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

作者：我是小白呀　　发布时间：2022-03-19 20:19:50　

标签：Java,时间复杂度,空间复杂度,数据结构

概述

从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.

Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

算法的衡量标准

当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量.

Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

时间复杂度

时间复杂度 (Time Complexity) 通常用 O(n) 表示, 用来描述一个算法运行的时间.

Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

时间复杂度 & 空间复杂度计算规则:

  • 用常数 1 代替运行中的所有加减, lim n->∞cn = ∞

  • 只保留最高项, lim n->∞ n^2 + an + b = lim n->∞ n^2

最优时间复杂度

最优时间复杂度指的是在最优的情况下算法需要的运行时间.

平均时间复杂度

平均时间复杂度是指所有可能的输入实例以等概率出现的情况下, 算法需要的运行时间.

最坏时间复杂度

最坏时间复杂度指的是在最坏的情况下算法需要的运行时间. 一般使用最坏时间复杂度作为时间复杂度.

O(1)

没有循环结构, 只有普通加减的代码时间复杂度为 O(1).

例如:


int i = 1;
int j = 2;
int k = i + j;  // 1+2=3

O(n)

循环 n 次的代码的时间复杂度为 O(n).

例子:


int sum = 0;
for (int i = 1; i < n; i++) {
   sum += i;
}

O(n^2)

两层循环嵌套的时间复杂度为 O(n^2). 如下例子, 需要进行 2n^2 次计算

例子:


int sum = 0;

for (int i = 1; i < n; i++) {
   for (int j = 0; j < n; j++) {
       sum += i;
       sum += j;
   }
}

O(logN)

2^n = N, 所以会循环 logN 次.

例子:


int sum = 0;

for (int i = 0; i < n; i++) {
   sum += i;
   i *= 2;
}

空间复杂度

空间复杂度 (Space Complexity) 定义为该算法所耗费的存储空间.

Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

O(1)

如果算法执行所需要的临时空间不会随着变量的大小而变化, 那么空间复杂度就为 O(1).

例子:


int i = 1;
int j = 2;
int k = i + j;  // 1+2=3

O(n)

长度为 n 的数组占用空间为 O(n).

例子:


int[] array = new int[n]

来源：https://iamarookie.blog.csdn.net/article/details/121782719

0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com