当前位置: 首页 > news >正文

数据结构第35节 性能优化 算法的选择

算法的选择对于优化程序性能至关重要。不同的算法在时间复杂度、空间复杂度以及适用场景上有着明显的差异。下面我将结合具体的代码示例,来讲解几种常见的算法选择及其优化方法。

示例 1: 排序算法

场景描述:

假设我们需要对一个整数数组进行排序。

算法选择:

对于较大的数据集,快速排序通常是一个不错的选择,因为它在平均情况下的时间复杂度为 O(n log n)。但对于小数据集,插入排序可能更优,因为它的常数因子较小。

代码示例:
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

示例 2: 查找算法

场景描述:

假设我们需要在一个有序数组中查找特定元素。

算法选择:

对于有序数组,二分查找是一个很好的选择,其时间复杂度为 O(log n)。

代码示例:
public class BinarySearch {public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}
}

示例 3: 动态规划

场景描述:

假设我们要解决斐波那契数列问题。

算法选择:

递归解决斐波那契数列问题会导致大量的重复计算。使用动态规划,我们可以存储中间结果,避免重复计算,从而将时间复杂度降低到 O(n)。

代码示例:
public class FibonacciDP {public static int fibonacci(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

示例 4: 图算法 - Dijkstra 算法

场景描述:

假设我们需要找到图中两点之间的最短路径。

算法选择:

Dijkstra 算法是一个非常有效的单源最短路径算法,其时间复杂度为 O((V+E)log V),其中 V 是顶点数,E 是边数。

代码示例:
import java.util.*;public class DijkstraAlgorithm {public static void dijkstra(Map<Integer, Map<Integer, Integer>> graph, int startNode) {int[] distances = new int[graph.size()];Arrays.fill(distances, Integer.MAX_VALUE);distances[startNode] = 0;PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));pq.offer(new int[]{startNode, 0});while (!pq.isEmpty()) {int[] current = pq.poll();int currentNode = current[0];int distanceToCurrent = current[1];if (distanceToCurrent > distances[currentNode]) continue;for (Map.Entry<Integer, Integer> entry : graph.get(currentNode).entrySet()) {int neighbor = entry.getKey();int weight = entry.getValue();int distanceToNeighbor = distanceToCurrent + weight;if (distanceToNeighbor < distances[neighbor]) {distances[neighbor] = distanceToNeighbor;pq.offer(new int[]{neighbor, distanceToNeighbor});}}}}
}

以上示例展示了如何根据不同的问题选择合适的算法,以及如何通过算法优化来提高程序的性能。每种算法都有其特定的适用场景和性能特征,因此在实际应用中,应根据具体情况灵活选择。

当然,我们可以进一步扩展上述算法的代码示例,添加更多实用的功能和增强代码的健壮性。接下来,我将为每一个示例增加额外的方法和注释,以帮助更好地理解和使用这些算法。

示例 1: 排序算法 - 快速排序扩展

我们将添加一个方法来检查数组是否已经排序,以及一个主函数来测试排序算法。

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static boolean isSorted(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {if (arr[i] > arr[i + 1]) {return false;}}return true;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}System.out.println("\nIs sorted? " + isSorted(arr));}
}

示例 2: 查找算法 - 二分查找扩展

我们将添加边界检查和异常处理,以确保数组不为空且是有序的。

public class BinarySearch {public static int binarySearch(int[] arr, int target) throws IllegalArgumentException {if (arr == null || arr.length == 0) {throw new IllegalArgumentException("Array is empty or null.");}if (!isSorted(arr)) {throw new IllegalArgumentException("Array must be sorted.");}int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}private static boolean isSorted(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {if (arr[i] > arr[i + 1]) {return false;}}return true;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9};int target = 5;try {int index = binarySearch(arr, target);System.out.println("Element found at index: " + index);} catch (IllegalArgumentException e) {System.out.println(e.getMessage());}}
}

示例 3: 动态规划 - 斐波那契数列扩展

我们将添加一个方法来计算斐波那契数列的所有项,并添加一个主函数来展示结果。

public class FibonacciDP {public static int fibonacci(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}public static int[] fibonacciSequence(int n) {int[] sequence = new int[n];for (int i = 0; i < n; i++) {sequence[i] = fibonacci(i);}return sequence;}public static void main(String[] args) {int n = 10;int[] sequence = fibonacciSequence(n);System.out.println("Fibonacci sequence up to " + n + ":");for (int num : sequence) {System.out.print(num + " ");}}
}

通过这些扩展,我们不仅增强了代码的功能性,还增加了异常处理和验证,使得代码更加健壮和实用。在实际开发中,这些额外的考虑对于确保程序的稳定性和正确性是非常重要的。

相关文章:

数据结构第35节 性能优化 算法的选择

算法的选择对于优化程序性能至关重要。不同的算法在时间复杂度、空间复杂度以及适用场景上有着明显的差异。下面我将结合具体的代码示例&#xff0c;来讲解几种常见的算法选择及其优化方法。 示例 1: 排序算法 场景描述: 假设我们需要对一个整数数组进行排序。 算法选择: …...

每天一个数据分析题(四百三十六)- 正态分布

X为服从正态分布的随机变量N(2, 9), 如果P(X>c)P(X<c), 则c的值为&#xff08;&#xff09; A. 3 B. 2 C. 9 D. 2/3 数据分析认证考试介绍&#xff1a;点击进入 题目来源于CDA模拟题库 点击此处获取答案 数据分析专项练习题库 内容涵盖Python&#xff0c;SQL&…...

跟我学C++中级篇——虚函数的性能

一、虚函数性能 一般来说&#xff0c;面向对象的设计中&#xff0c;继承和多态是其中两个非常重要的特征。从使用的过程来看&#xff0c;一般应用到继承的&#xff0c;使用多态的可能性就非常大。而多态的实现有很多种&#xff0c; 但开发者通常认为的多态&#xff08;动多态&…...

trl - 微调、对齐大模型的全栈工具

文章目录 一、关于 TRL亮点 二、安装1、Python包2、从源码安装3、存储库 三、命令行界面&#xff08;CLI&#xff09;四、如何使用1、SFTTrainer2、RewardTrainer3、PPOTrainer4、DPOTrainer 五、其它开发 & 贡献参考文献最近策略优化 PPO直接偏好优化 DPO 一、关于 TRL T…...

GuLi商城-商品服务-API-品牌管理-品牌分类关联与级联更新

先配置mybatis分页&#xff1a; 品牌管理增加模糊查询&#xff1a; 品牌管理关联分类&#xff1a; 一个品牌可以有多个分类 一个分类也可以有多个品牌 多对多的关系&#xff0c;用中间表 涉及的类&#xff1a; 方法都比较简单&#xff0c;就不贴代码了...

【linux】服务器ubuntu安装cuda11.0、cuDNN教程,简单易懂,包教包会

【linux】服务器ubuntu安装cuda11.0、cuDNN教程&#xff0c;简单易懂&#xff0c;包教包会 【创作不易&#xff0c;求点赞关注收藏】 文章目录 【linux】服务器ubuntu安装cuda11.0、cuDNN教程&#xff0c;简单易懂&#xff0c;包教包会一、版本情况介绍二、安装cuda1、到官网…...

在 Apifox 中如何高效批量添加接口请求 Body 参数?

在使用 Apifox 进行 API 设计时&#xff0c;你可能会遇到需要添加大量请求参数的情况。想象一下&#xff0c;如果一个接口需要几十甚至上百个参数&#xff0c;若要在接口的「修改文档」里一个个手动添加这些参数&#xff0c;那未免也太麻烦了&#xff0c;耗时且易出错。这时候&…...

专业PDF编辑工具:Acrobat Pro DC 2024.002.20933绿色版,提升你的工作效率!

软件介绍 Adobe Acrobat Pro DC 2024绿色便携版是一款功能强大的PDF编辑和转换软件&#xff0c;由Adobe公司推出。它是Acrobat XI系列的后续产品&#xff0c;提供了全新的用户界面和增强功能。用户可以借助这款软件将纸质文件转换为可编辑的电子文件&#xff0c;便于传输、签署…...

车载音视频App框架设计

简介 统一播放器提供媒体播放一致性的交互和视觉体验&#xff0c;减少各个媒体应用和场景独自开发的重复工作量&#xff0c;实现媒体播放链路的一致性&#xff0c;减少碎片化的Bug。本文面向应用开发者介绍如何快速接入媒体播放器。 主要功能&#xff1a; 新设计的统一播放U…...

StarRocks on AWS Graviton3,实现 50% 以上性价比提升

在数据时代&#xff0c;企业拥有前所未有的大量数据资产&#xff0c;但如何从海量数据中发掘价值成为挑战。数据分析凭借强大的分析能力&#xff0c;可从不同维度挖掘数据中蕴含的见解和规律&#xff0c;为企业战略决策提供依据。数据分析在营销、风险管控、产品优化等领域发挥…...

VUE中setup()

在Vue中&#xff0c;setup() 函数是Vue 3.0及更高版本引入的一个重要特性&#xff0c;它是Composition API的入口点。setup() 函数用于初始化组件的状态和逻辑&#xff0c;包括定义响应式数据、方法和生命周期钩子。以下是关于setup() 函数的详细解释&#xff1a; 1. 作用与特…...

【单元测试】SpringBoot

【单元测试】SpringBoot 1. 为什么单元测试很重要&#xff1f;‼️ 从前&#xff0c;有一个名叫小明的程序员&#xff0c;他非常聪明&#xff0c;但有一个致命的缺点&#xff1a;懒惰。小明的代码写得又快又好&#xff0c;但他总觉得单元测试是一件麻烦事&#xff0c;觉得代码…...

分布式搜索引擎ES-elasticsearch入门

1.分布式搜索引擎&#xff1a;luceneVS Solr VS Elasticsearch 什么是分布式搜索引擎 搜索引擎&#xff1a;数据源&#xff1a;数据库或者爬虫资源 分布式存储与搜索&#xff1a;多个节点组成的服务&#xff0c;提高扩展性(扩展成集群) 使用搜索引擎为搜索提供服务。可以从海量…...

TCP三次握手与四次挥手详解

1.什么是TCP TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议&#xff09;是一种面向连接的、可靠的、基于字节流的通信协议&#xff0c;属于互联网协议族&#xff08;TCP/IP&#xff09;的一部分。TCP 提供可靠的、顺序的、无差错的数据传输服务&…...

【Windows】操作系统之任务管理器(第一篇)

一、操作系统简介 Windows操作系统是由微软公司&#xff08;Microsoft&#xff09;开发的一款图形操作系统&#xff0c;它以其强大的功能和广泛的用户基础&#xff0c;成为了目前世界上用户使用最多、兼容性最强的操作系统之一。以下是关于Windows操作系统的详细介绍&#xff…...

图同构的必要条件

来源&#xff1a;离散数学...

Django获取request请求中的参数

支持 post put json_str request.body # 属性获取最原始的请求体数据 json_dict json.loads(json_str)# 将原始数据转成字典格式 json_dict.get("key", "默认值") # 获取数据参考 https://blog.csdn.net/user_san/article/details/109654028...

kotlin compose 实现应用内多语言切换(不重新打开App)

1. 示例图 2.具体实现 如何实现上述示例,且不需要重新打开App ①自定义 MainApplication 实现 Application ,定义两个变量: class MainApplication : Application() { object GlobalDpData { var language: String = "" var defaultLanguage: Strin…...

记录些MySQL题集(16)

MySQL 存储过程与触发器 一、初识MySQL的存储过程 Stored Procedure存储过程是数据库系统中一个十分重要的功能&#xff0c;使用存储过程可以大幅度缩短大SQL的响应时间&#xff0c;同时也可以提高数据库编程的灵活性。 存储过程是一组为了完成特定功能的SQL语句集合&#x…...

【算法基础】Dijkstra 算法

定义&#xff1a; g [ i ] [ j ] g[i][j] g[i][j] 表示 v i v_i vi​ 到 $v_j $的边权重&#xff0c;如果没有连接&#xff0c;则 g [ i ] [ j ] ∞ g[i][j] \infty g[i][j]∞ d i s [ i ] dis[i] dis[i] 表示 v k v_k vk​ 到节点 v i v_i vi​ 的最短长度&#xff0c; …...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...