Algorithms Unlocked

标签: 算法总结

1.what Are Algorithms and why should you care?

1.1Algorithms-what?

俗称:算法是完成任务的一组步骤。

1.2Algorithms-get?

给一个问题一个输入,他总是应该为该问题提供正确的解决方案,并且应该同时有效的利用计算资源。

1.3Algorithms-correctness

给出对应问题的正确解。(如果能够控制错误解的执行频率,我们可以接受计算机算法可能会产生错误的答案)

Loop invariants
循环不变式可以帮助我们辩解算法的正确性。
循环不变式的三条性质:
初始化:循环的第一次迭代之前,它为真。
保持:如果循环的某次迭代之前它为真,那么下次迭代之前它仍为真。
终止:在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法是正确的。

正确性correctness是另一类算法的棘手问题,称为近似算法
近似算法适用于优化问题。

1.3Algorithms-Resource usage

编写程序(算法)时,有正确答案前提下,我们往往考虑以下几个方面。
时间复杂度:效率度量。其除了算法编程语言,还依赖于其他的外在因素:计算机性能等。

2.How to Decribe and Evaluate Compute Algorithms?

2.1How to Decribe Compute Algorithms?

将计算机算法描述为使用常用编程语言(例如Java,C,C++,python等)的可运行程序。

2.2How to Evaluate Compute Algorithms?

常用时间复杂度与空间复杂度评估算法
时间复杂度与空间复杂度

2.3Recurion

递归:其实就是函数调用其本身来实现某些算法。
每个递归定义必须至少有一个条件,当满足条件时递归不再进行。 递归的优点:结构更清晰,代码更简洁,更容易让人理解,从而减少代码的阅读时间。
例子:计算n!
伪代码
在这里插入图片描述
python

def factional(n):
    if n==0:
        return 1
    else:
        return n*factional(n-1)
    

3. Algorithms for Sorting and Searching

3.1Algorithms-search(搜索)

3.1.1线性搜索linear-search

(遍历所有的数据)
伪代码:
在这里插入图片描述
python

def linear_search(A,x):
    n=len(A)
    answer = "NOT FOUND"
    for i in range(n):
        if A[i]==x:
            answer=i
    return answer

递归法实现线性搜索
在这里插入图片描述

def Recursive_linear_search(A,i,x):
    n=len(A)
    if i>n:
        return "NOT-FOUND"
    else :
        if A[i]==x:
            return i
        else:
            return  Recursive_linear_search(A,i+1,x)   

输入函数中i=0

3.1.2较好的线性搜索better-linear-search

(找到值就不再遍历,跳出循环)
伪代码
在这里插入图片描述
python

def better_linear_search(A,x):
    n=len(A)
    for i in range(n):
        if A[i]==x:
            return i
    return print("NOT FOUND")
    

3.1.3哨兵线性搜索sentinel-linear-search

(在最后的位置上放置一个空盒子,并令这个变量等于x即我们要寻找的值:这样可以减少判断i《n的循环)
伪代码
在这里插入图片描述
python

def sentinel_linear_search(A,x):
    n=len(A)
    last=A[n-1]#b保存数组最后一个元素
    A[n-1]=x#用x替换数组最后一个元素
    i=0
    while A[i]!=x:
        i+=1
    A[n-1]=last#还原数组最后一个元素
    if i<n-1 or A[n-1]==x:
        return i 
    else:
        print("NOT FOUND")

3.1.4二分查找/二分搜索Binary search

(要求数组已排序)
假设表中元素是有序的,将表的中间位置的关键字与所需的关键字比较,相等则成功,否则分为前后两个子表,若所需的值大于中间元素,则在后半部分查找,否则在前半部分查找。重复上述过程,直到查询到结果。需要两个指针p,r
优点:比较次数少,速度快
缺点:要求待查表为有序表。
时间复杂度:O(logn)
伪代码
在这里插入图片描述

#非递归实现
import numpy as np
def binary_search(A,x):
    A=np.sort(A)#先将A排序
    n=len(A)
    p=1#p:头指针
    r=n-1#r:尾指针
    while p<=r:
        q=(p+r)//2#//符号:商取整
        if A[q]==x:
            return q
        elif A[q]>x:
            r=q-1
        else:
            p=q+1
    return print("NOT FOUND")
#递归实现(p,r)一般刚开始是(0,len(A)_1)也就是列表中第一个与最后一个位置
def recursive_binary_search(A,p,r,x):
    A=np.sort(A)#先将A排序
    if p>r:
        return print("NOT FOUND")
    else:
        q=(p+r)//2
        if A[q]==x:
            return q
        elif A[q]>x:
            return recursive_binary_search(A,p,q-1,x)
        else:
            return recursive_binary_search(A,q+1,r,x)
   

3.2Algorithms-sort(搜索)

十大经典排序算法

4.A Lower Bound for Sorting and How to Beat It

三级目录

版权声明:本文为weixin_45666566原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45666566/article/details/105856105

智能推荐

ActiveMQ学习4-ActiveMQ的安全机制和集群模式

ActiveMQ的安全机制和集群模式 20 ActiveMQ安全机制 20.1 Web 控制台安全 20.2 消息服务器Broker安全 21 ActiveMQ主从集群 21.1 使用集群的重要性 20.2 主从集群的方式 20.2.1 shared filesystem Master-Slave方式主从集群 20.2.2 shared database Master-Slave方式主从集群 20...

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

猜你喜欢

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...