算法那些事儿

什么是计算机算法?

算法是计算机可以用来解决特定问题的指令列表。算法用于计算的所有领域,它们旨在以有效的方式解决问题。

算法的设计取决于它需要解决的问题的复杂性。对于简单的问题,蛮力可能是可行的。然而,对于更复杂的问题,需要更复杂的算法。

计算机算法无处不在

算法是我们所有数字生活的支柱。它们帮助我们更快、更有效地做出决策。

日常生活中用到的算法例子,比如谷歌搜索引擎、亚马逊推荐系统、Netflix电影推荐系统,算法无处不在!

高效算法和大 O(n):

优化过程还取决于算法的类型和复杂性。在某些情况下,优化算法可能需要几天或几周的时间,而在其他情况下,可能只需要几小时或几分钟。

当涉及到 Big O(n) 时,时间和空间变量是最重要的。算法是软件工程和计算资源的重要组成部分。对其性能至关重要的组件之一是大 O(n) 符号。此短语中的字母 O(n) 限定了特定算法正在执行多少操作,其中较小的数字意味着更快的执行时间。还取决于我们谈论的 (n) 数量。Big O 专注于最坏的情况。

一项操作的突出之处在于它找到所需结果的效率。操作的大小是它对空间的依赖性以检索所需的结果。

您的操作输入越多,它就会变得越慢。有几种不同的常见类型的“大 O”符号表示输入如何影响操作的效率。其中包括 O(n)、O(1),这是最有效的算法,以及 O(log n) 等等……

[图片上传失败...(image-8e00a4-1667142054392)]

算法如何工作?

算法用于对列表指令进行排序并找到给定问题的最佳可能解决方案或最优解决方案。排序算法是数据处理中最常用的算法。它们通过保持排序来帮助组织数据点,以便可以轻松访问。

排序算法的不同方法的列表是不完整的,没有提到线性排序,它不是真正的算法,而是一种可以与任何其他排序方法一起使用的技术。

可分为简单和复杂:

  • 简单的排序算法称为“冒泡排序”和“插入排序”。
  • 复杂的排序算法包括“快速排序”、“合并排序”和“堆排序”。

算法的复杂性

该算法可以通过两种方式来衡量:

算法的时间复杂度

时间复杂度是算法运行时间的上限。它用函数、渐近符号和常数值表示。这可以写成方程、图形或表格的形式,以显示函数对自变量的依赖性。O(n) 的时间复杂度意味着该算法将在与 n 个相关的一系列逻辑步骤中完成。

算法的空间复杂度

空间复杂度是执行算法需要多少空间的量度。算法的空间复杂度可以通过多种方式测量,包括:迭代次数、每次操作处理的位数或每次迭代处理的字数。O(n) 算法在输入大小上是线性的。这意味着它需要与输入大小相关的时间,直到某个最大工作量。

解决问题的多种技术?

解决问题的方法有很多种,可以使用不同的标准进行分类。

最常见的类型是:

  1. 分而治之:是解决问题的聪明方法。首先,将问题细分为更小的子问题,解决那些更小的问题,并将所有解决方案组合成问题的最终解决方案。
  2. 蛮力:尝试所有可能的解决方案,直到找到满意的解决方案。
  3. 随机化:在计算过程中使用随机数来找到问题的解决方案。
  4. 贪婪:在较小的零件上寻找有效的解决方案,然后将此最佳解决方案扩展到其余零件
  5. 递归:用于通过解决更小、更简单的变化来解决问题的更大和更困难的版本。
  6. 回溯:是一种计算机编程技术,将问题划分为子问题,然后将每个问题带到一个尝试的解决方案。如果没有达到所需的解决方案,它将通过找到一条在问题中向前移动的路径来向后工作。
  7. 动态规划:专注于解决一系列简单问题中的复杂问题,这些问题只解决一次,而不是为每个问题重新计算。在至少计算一次之后,您需要将其存储在某个地方以便在必要时重新调用它
  8. 指针遍历或寻路:在搜索图或网络时,使用经过验证的搜索算法很重要。指针遍历是一种搜索算法,可用于查找从图的一个节点到另一个节点的最短路径。例如,如果我们想使用指针遍历找到从节点 1 到节点 2 的最短路径,那么我们将首先寻找节点 1 的最近邻居,然后,如果没有,则寻找节点父节点的最近邻居
  9. 哈希表:哈希表算法用于多种用途,例如碰撞检测和寻路。碰撞检测是当您要确保两个对象不相互交叉时,而寻路是计算两个或多个点之间的最短距离的过程。

我们遇到了问题

如何用简单的英语解决它?

首先要做的是阅读问题并确保您了解说明要求您做什么。

接下来,确定问题中给定的所有变量的可能值,并尝试为每个变量提出一个逻辑解决方案。

最后,试着写出一个算法,从文字而不是代码开始,写出每个程序员都知道的被称为“伪代码”的东西

什么是伪代码?

当我们考虑编程时,经常会看到伪代码。它是程序员用来设计算法或另一个系统功能的语言的描述性词。

这种编程语言可以使用普通语言的结构约定,但它是为人类阅读而不是机器阅读而设计的。

算法示例

这是一个例子,说明我们在面对问题时如何思考以及如何解决问题。

当然这只是我的观点,但我希望你能从中得到一些东西。我会从leetcode得到这个问题

这个关于字谜的问题,字谜是通过重新排列另一个单词的字母而创建的单词。新单词将始终具有原始单词的所有原始字母,但顺序不同。

示例 1

输入: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

您已阅读说明、查看示例并在 Google 上进行了研究。所有这些都应该让您提前为所请求的内容和代码行中包含的内容做好准备。

当然,您仍在尝试弄清楚如何将其放在代码中,但是现在您对解决方案有了一定的了解,您可以着手处理它。

我的想法逐步过程如下:

1. 我可以从输入数据中得到每个单词的一个实例。

2. 这个实例应该让它成为默认实例,并且它应该被排序。

3. 同样,此默认实例将是收集其他实例的键值。

4. 该集合是一个数组,其中的这些值来自已排序的键值。

5. 如果我找不到多个实例,那么我将返回我得到的任何实例。

现在让我们通过想象我们编写了几行代码来进一步分解它。但是这段代码将是一个伪代码。

所以我们需要一种可以存储键值对的表。键将是单词的默认排序实例,值将是同一单词的相同字符内的多个实例值的数组。如果我们找不到相同单词的任何其他实例,那么我们将其单独放入数组中。

所以,

遍历输入数组

对每个字符串进行排序,使其成为我们上面讨论的默认键

键是否存在于哈希表中,然后将未排序的版本放入它的值中

如果没有,则在循环中使用当前值创建一个数组

Javascript中的源代码:

function groupAnagrams(strs) {
//creating the Hash Table
const hashTable = {}
  for (let i = 0; i < strs.length; i++){ //Loop through the input list

  // Creating the default key by sorting out the value from each string

  // To use the Sort method in JS, you need to use it on an array.

  // By using the Split() method, you create an array from this current value that you standing on.

  // By using the join() method, you recreate the string from the group of characters you created with the split() method above.

    const defKey = strs[i].split('').sort().join('')

    if (hashTable[defKey]){ 
  //Checking if the hash table has this value if yes, push the current value which is in that case going to be  different instance from the sorted default instance.

    hashTable[defKey].push(strs[i])

    } else {

    // if not just initialize it with an array

    hashTable[defKey] = [strs[i]]

    }

  }
//Another great method in JS to help you flat all arrays created in the values of hash Table into one array
return Object.values(hashTable)
};

Python中的源代码:

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

推荐阅读更多精彩内容

  • (2022.10.30 Sun)生成树(Minimal Spanning Tree,MST)的概念针对连通图而提出...
    Mc杰夫阅读 144评论 0 0
  • 基于课堂生根,助推学生空间观念发展——《平行四边形的面积》研课分析 涂茨小学 史晓艳 一、教材分析 《平行四边形的...
    火柴叙事阅读 149评论 0 0
  • 今天开讲单乘多 主讲老师徐思源 合并顺序记心怀,按某字母降幂来。 这样你就不漏项,结果自然有序排。 今天@所有人 ...
    千里马会军阅读 192评论 0 0
  • 雷素敏坚持原创分享1623天。父母的觉醒:身为父母,我们不能错误地认为自己有权决定孩子是什么样的人。我们凭什么来评...
    风雨之前阅读 114评论 0 1
  • 《《好好学习》读后感 学习其实是对知识进行管理的过程。什么是知识,知识不是今天看了一本书,其中的观点对自己有启发,...
    更清新的2023阅读 54评论 0 0