算法入门

最近在研究算法,发现其实算法也并不是特别难,只要抓住算法的核心思想,再静下心来,都可以自己实现的。在计算机领域,有一些常见的而且又经常使用的算法,这些算法我们应该掌握,比如常见的排序算法;还有一些算法就是特定领域中经常使用的算法了,这些算法我们只有必须使用时再去学习使用就行了,比如图像处理中的快速傅里叶变换算法。

Algorithm.jpg

算法定义

让我们来看看算法的定义吧。(以下定义摘自中文维基百科)

在数学和计算机科学/算学之中,算法/演算法/算则法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

算法中的指令描述的是一个计算,当其运行时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。

算法的特征

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳:

  • 输入:一个算法必须有零个或以上输入量。
  • 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
  • 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地匹配要求或期望,通常要求实际运行结果是确定的。
  • 有限性:依据图灵的定义,一个算法是能够被任何图灵完备系统模拟的一串运算,而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
  • 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

算法的基本要素

算法的核心是创建问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。

说起到算法,那么怎样衡量一个算法的好坏呢?答案是通过两方面来考虑,一是从时间上来考虑,也就是所谓的时间复杂度; 还有就是从空间上来考虑,也就是空间复杂度

时间复杂度

  • 算法的时间复杂度是指算法需要消耗的时间资源。

一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做T(n)=O(f(n))

算法执行时间的增长率与f(n) 的增长率正相关,称作渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。

常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

空间复杂度

  • 算法的空间复杂度是指算法需要消耗的空间资源。

其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

注意,如果你特别在意算法的时间,在条件允许的情况下可以考虑牺牲空间,也就是所谓的拿空间换取时间。

算法设计的方法

另外,对于算法的设计,通常有以下几种方法。

  • 穷举法
  • 分治法
  • 动态规划法
  • 贪婪算法
  • 线性规划法

这些方法在此就不深入讲解了,因为每一个都可以单独拿出长长的一大篇文章来讲解,不过,我后面会继续深入普及这方面的知识的。

算法实现的方法

除了了解到算法的常见设计方法,那么还有哪些常见的实现方法呢。

  • 一般方法
  • 递归方法
  • 迭代方法

好了讲了这么多理论,还是用一个例子来解释下算法到底是什么。

求最大公约算法

问题:

求两个自然数的最大公约数 设两个变量M和N

解题步骤:

1.如果M < N,则交换M和N
2.M被N除,得到余数R
3.判断R=0,正确则N即为“最大公约数”,否则下一步
4.将N赋值给M,将R赋值给N,重做第一步。

代码实现

void swapi(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int gcd(int m, int n)
{
    int r;
    do {
        if (m < n)
            swapi(&m, &n);
        r = m % n;
        m = n;
        n = r;
    } while (r);
    return m;
}

好了就讲这么多了,如果有什么问题可以在下面评论或者发私信给我。

参考文章

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,376评论 6 491
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,126评论 2 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 156,966评论 0 347
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,432评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,519评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,792评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,933评论 3 406
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,701评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,143评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,488评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,626评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,292评论 4 329
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,896评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,742评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,977评论 1 265
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,324评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,494评论 2 348

推荐阅读更多精彩内容

  • 很多人都听说过加密算法,包括ECC、ECDH或者ECDSA。ECC是Elliptic Curve Cryptogr...
    糖酱桑阅读 55,067评论 20 73
  • 每个人都有灵魂。每个人的灵魂的任务是不一样。她需要在她的生命路上去吸取
    她总阅读 88评论 0 0
  • 外界的波澜,内心的澎湃,年轻的心,不安的心,此情此景,记忆深刻,我是怎么了,一个角落里的沉思者。
    角落的沉思者阅读 176评论 5 2
  • "生成小学校长的智慧"是吴瑞莲老校长今天给我们校长培训班的授课主题。吴老八十高龄,对教育事业的忠爱尽显在她...
    HannahMerryn阅读 325评论 0 0
  • 我想这应该是与,曹操‘恃才’有关,我们先从杨修分别参与了什么事件说起。 1.阔门事件;曹操让人造一座花园,造...
    指针指向你心脏阅读 396评论 0 0