Rust 数据结构与算法:1算法分析之乱序字符串检查

2024-02-16 20:52

本文主要是介绍Rust 数据结构与算法:1算法分析之乱序字符串检查,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Rust 数据结构与算法

一、算法分析

算法是通用的旨在解决某种问题的指令列表。

算法分析是基于算法使用的资源量来进行比较的。之所以说一个算法比另一个算法好,原因就在于前者在使用资源方面更有效率,或者说前者使用了更少的资源。

●算法使用的空间指的是内存消耗。算法所需的内存通常由问题本身的规模和性质决定,但有时部分算法会有一些特殊的空间需求。

●算法使用的时间指的是算法执行所有步骤经过的时间,这种评价方式被称为算法执行时间。

1、大 O 分析法

在时间方面,我们使用函数T表示总的执行次数,T(n) = 1 + n,参数n通常被称为问题的规模,T(n)则是解决规模为n的问题所要花费的时间。

在空间方面,我们使用函数S表示总的内存消耗,S(n) = 2,参数n仍然表示问题的规模,但S(n)已经和n无关了。

但大多数时候,我们主要分析时间复杂度,因为空间往往不好优化。

另外,随着摩尔定律的发展,存储越来越便宜,空间越来越大,这时候时间才是最重要的,因为时间无价。

在这里插入图片描述

一些常见的数量级函数

在这里插入图片描述

复杂度曲线

当n很小时,函数彼此间并不能很好地区分,很难判断哪个是主导函数。但随着n变大,关系就比较明确了,一般情况下(n > 10),O(2n) > O(n3) > O(n2) > O(n log n) > O(n) >O(log n) > O(1)。这对于我们设计算法很有帮助,因为对于每个算法,我们都能计算其复杂度。

假设有这样一个算法,已确定操作步骤的数量是T(n) = 6n2 +37n+996。当n很小时,例如1或2,常数996似乎是函数的主要部分。然而,随着n变大,n2这一项变得越来越重要。事实上,当n很大时,其他两项在最终结果中所起的作用已变得不重要。当n变大时,为了近似T(n),我们可以忽略其他项,只关注6n2。系数6也变得不重要。此时,我们说T(n)具有的复杂度数量级为n2或O(n2)。

T(n) = n + 1。当n变大时,常数1对于最终结果将变得越来越不重要。如果我们要找的是T(n)的近似值,则可以删除1,此时运行时间为O(T(n)) = O(n + 1) = O(n)。注意,1对于T(n)肯定是重要的,但是当n变大时,不管有没有n,O(n)都是准确的。比如,对于T(n) = n3 + 1,当n为1时,T(n) = 2,此时舍掉1就不合理,因为这样相当于丢掉一半的运行时间。但是当n等于10时,T(n) = 1001,此时1已经不重要,即便舍掉,T(n)= 1000也仍然是一个很准确的指标。对于S(n)来说,因为其本身就是常数,所以O(S(n)) = O(2) =O(1)。大O分析法只表示数量级,因此虽然实际上是O(2),但其数量级是常量,可用O(1)代替。

2、乱序字符串检查

一个展示不同数量级复杂度的例子是乱序字符串检查。乱序字符串是指一个字符串s1只是另一个字符串s2的重新排列。例如,“heart”和“earth”是乱序字符串,“rust”和“trus”也是乱序字符串。

为简单起见,假设要讨论的两个字符串具有相同的长度,并且只由26个小写字母组成。我们的目标是写一个函数,它接收两个字符串作为参数并返回它们是不是乱序字符串的判断结果。

1、穷举法

解决乱序字符串问题的最笨方法是穷举法,也就是把每种情况都列举出来。当为字符串s1生成所有可能的乱序字符串时,第1个位置有n种可能,第2个位置有n-1种可能,第3个位置有n-3种可能,以此类推,总共有n×(n−1)×(n−2)×…×3×2×1种可能,即n!

2、检查法

乱序字符串问题的第二种解决方案是检测第一个字符串中的字符是否出现在第二个字符串中。如果检测到每个字符都存在,那么这两个字符串一定是乱序的。

代码:

/** @Description:* @Author: tianyw* @Date: 2024-02-15 10:22:41* @LastEditTime: 2024-02-15 10:35:46* @LastEditors: tianyw*/
// 时间复杂度为 O(n²)
fn anagram_solution2(s1: &str, s2: &str) -> bool {if s1.len() != s2.len() {return false;};// 将 s1 和 s2 的字符分别添加到 vec_a 和 vec_b 中let mut vec_a = Vec::new();let mut vec_b = Vec::new();for c in s1.chars() {vec_a.push(c)}for c in s2.chars() {

这篇关于Rust 数据结构与算法:1算法分析之乱序字符串检查的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/715680

相关文章

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重