首页 > 其他分享 >时间复杂度、线性查找

时间复杂度、线性查找

时间:2022-09-24 20:23:26浏览次数:54  
标签:arr int 复杂度 查找 线性 排序

  • 排序算法时间复杂度比较
稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
内排序:所有排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
n: 数据规模
k: “桶”的个数
In-place:    不占用额外内存
Out-place: 占用额外内存
  • 查找算法
1) 顺序(线性)查找
2) 二分查找/折半查找
3) 插值查找
4) 斐波那契查找
  • 线性查找算法代码案例
public class SeqSearch {

	public static void main(String[] args) {
		int arr[] = { 1, 9, 11, -1, 34, 89 };// 没有顺序的数组
		int index = seqSearch(arr, -11);
		if(index == -1) {
			System.out.println("没有找到到");
		} else {
			System.out.println("找到,下标为=" + index);
		}
	}

	/**
	 * 这里我们实现的线性查找是找到一个满足条件的值,就返回
	 * @param arr
	 * @param value
	 * @return
	 */
	public static int seqSearch(int[] arr, int value) {
		// 线性查找是逐一比对,发现有相同值,就返回下标
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] == value) {
				return i;
			}
		}
		return -1;
	}

}

标签:arr,int,复杂度,查找,线性,排序
From: https://www.cnblogs.com/chniny/p/16726396.html

相关文章

  • 力扣1095——山脉数组中查找目标值
    1095.山脉数组中查找目标值难度困难(这是一个 交互式问题 )给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的......
  • 二分查找模板
    //arr数组升序//n是数组长度,也就是lr正好是数组的左右的第一个和最后一个intl=0,r=n-1;intmid;while(l<=r){mid=(l+r)/2;if(arr[mid]==......
  • 尾递归与非尾递归(线性递归)
    1尾递归与非尾递归区别非尾递归(线性递归):当数量很大时,会造成栈溢出。因为每次递归调用时,递归函数中的参数,局部变量等都要保存在栈中。尾递归:return时只调用自身,不能有额......
  • 面向复杂度架构设计
    1、常见架构设计   面向模式、面向风险、DDD、面向复杂度2、面向模式(有书能买posa)   使用成熟的方案,模式很多,应用很难,高度抽象,不接地气。3、面向风险(书:恰......
  • linux文件查找
    find的用法findpath-option[-print][-exec-okcommand]{}\;find.-name"*.txt"-print:找到当前路径下所有的.txt文件并输出type为l的文......
  • 二分查找步骤及问题总结
    二分查找参数:有序数组arr(这里按升序来讲),待搜索的值target步骤定义左边界left和有边界right获取中间索引(整数)mid=(left+right)/2,注意:js只有小数,mid需要再取整......
  • 【线性dp】 [SCOI2009]粉刷匠
    点个关注点个赞吧一道比较简单的线性dp题目前置知识:会手推一些简单的状态转移方程、较为熟练地掌握背包问题模型[SCOI2009]粉刷匠题目描述windy有\(N\)条木......
  • 时间频度、时间复杂度
    算法的时间复杂度时间频度忽略常数项忽略低次项忽略系数......
  • sql练习--查找山东大学或者性别为男生的信息
    描述题目:现在运营想要分别查看学校为山东大学或者性别为男性的用户的device_id、gender、age和gpa数据,请取出相应结果,结果不去重。 示例:user_profileiddevice_i......
  • 基础线性代数
    基础线性代数矩阵变换将向量逆时针旋转90°:左乘0-110将向量延长至两倍:左乘2002矩阵乘法#include<bits/stdc++.h>#defineMod1000000007#definema......