web前端算法简介

• 前端web算法
  • 常见的前端web算法内容
• 数据结构
  • 常用的数据结构包括：
• 算法
  • 算法与逻辑
    • 算法：
    • 逻辑：
    • 联系：
• 时间复杂度
  • 时间复杂度是什么
  • 时间复杂度能干什么
  • 时间复杂度表示方法
    • O1 复杂度 – 除了循环和递归意外情形
    • On 复杂度 --单层循环/遍历
    • On^2 复杂度 – 循环嵌套
    • Olog n 复杂度
• 空间复杂度
  • 空间复杂度是什么
  • 时间复杂度表示方法
    • O1 复杂度
    • On 复杂度 – 循环嵌套
    • On^2 复杂度 – 循环嵌套
• 时间复杂度与空间复杂度
  • 区分与联系
  • 衡量标准有什么区别
    • 时间复杂度的衡量标准：
      • 执行时间：
      • 操作次数：
      • 输入规模：
    • 空间复杂度的衡量标准：
      • 内存占用：
      • 额外空间：
      • 输入规模：
    • 总结
  • 衡量标准举例
    • 时间复杂度的举例
    • 空间复杂度的举例
  • 二者举例
    • 时间复杂度的举例：
      • 线性搜索：
      • 插入排序：
    • 空间复杂度的举例：
      • 快速排序：
      • 动态规划：

前端web算法

前端web算法涉及到一系列在前端开发中常用的算法和数据结构，主要用于优化页面性能、提高用户体验和解决前端开发中的实际问题。

常见的前端web算法内容

常见的前端web算法内容包括但不限于：

1. 搜索算法（二分查找、线性搜索等）
2. 排序算法（冒泡排序、快速排序、归并排序等）
3. 数据结构（数组、链表、栈、队列、树等）
4. 图算法（广度优先搜索、深度优先搜索等）
5. 字符串算法（字符串匹配、正则表达式等）
6. 动态规划（解决页面布局、优化资源加载等）

举例说明：

在前端开发中，可能需要使用二分查找算法来在有序数组中快速查找某个值的位置，以提高搜索效率。

又或者，使用动态规划算法来优化页面布局，根据不同设备尺寸和分辨率调整元素布局，以实现响应式设计。

这些算法和数据结构的应用能够帮助前端开发者解决实际问题，提高页面性能和用户体验。

数据结构

计算机存储或者组织数据的方式

数据结构是指在计算机中组织和存储数据的方式。

它包括了一系列的数据元素，以及这些数据元素之间的关系和操作。

数据结构能够帮助我们有效地管理和操作数据，同时也可以影响算法的设计和效率。

常见的数据结构包括数组、链表、栈、队列、树等。

这些数据结构在不同的情况下都有不同的优势和适用性。

常用的数据结构包括：

1. 数组（Array）：一种线性结构，可以存储相同类型的元素，通过索引访问元素。
2. 链表（Linked List）：由节点组成的线性结构，每个节点包含数据和指向下一个节点的引用。
3. 栈（Stack）：一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作。
4. 队列（Queue）：一种先进先出（FIFO）的数据结构，允许在一端插入，在另一端删除。
5. 树（Tree）：一种非线性结构，包含父子关系的节点，如二叉树、二叉搜索树等。
6. 图（Graph）：由节点和边组成的非线性结构，用于表示实体之间的关系。
7. 哈希表（Hash Table）：通过哈希函数将键映射到值的数据结构，用于快速查找和插入。
8. 堆（Heap）：一种特殊的树形数据结构，常用于实现优先队列和堆排序。

这些数据结构在计算机科学和软件开发中都有广泛的应用。

更多详细内容，请微信搜索“前端爱好者“， 戳我 查看 。

算法

解决问题的方式

算法与逻辑

算法：

• 定义： 算法是解决特定问题或执行特定任务的一系列步骤和规则。它是一种精确定义的计算过程，可以用来解决数学问题、处理数据、自动化推理等。
• 特点： 算法通常是有限的、确定的、可行的，并且能够产生正确的结果。
• 作用： 算法在计算机科学中起着关键作用，用于搜索、排序、优化、数据分析等各种领域的问题。

逻辑：

• 定义： 逻辑是思考和推理的规则和原则，用于有效地处理信息和形成结论。它涉及判断、推理和论证。
• 特点： 逻辑是一种系统性的方法，用来对信息和观点进行分析和评估，并从中得出合乎逻辑的结论。
• 作用： 逻辑是哲学、数学、计算机科学等领域的基础，它帮助我们正确地推理、证明和解决问题。

联系：

• 关联： 算法需要符合逻辑规则，因为一个良好的算法应当是合乎逻辑的、能够产生正确结果的。
• 关系： 逻辑提供了分析问题和设计算法的方法，而算法则是根据逻辑规则实现具体任务的步骤。

总的来说，逻辑提供了思考和推理问题的基本规则，而算法则是按照这些规则设计和执行特定任务的步骤。

在计算机科学中，逻辑和算法是紧密相关的，二者共同促进了程序设计和问题解决的发展。

时间复杂度

时间复杂度是什么

执行当前算法所 “需花费的时间”

时间复杂度是衡量算法执行时间所需操作次数的度量。它通常用大O符号来表示，例如O(n)、O(n^2)等。时间复杂度越低，算法执行所需的时间就越短。

常见的时间复杂度包括：

1. O(1)：常数时间复杂度，表示算法的执行时间不随输入规模变化而变化，例如对单个元素的访问。
2. O(log n)：对数时间复杂度，通常出现在二分查找等算法中。
3. O(n)：线性时间复杂度，算法的执行时间与输入规模成正比，例如遍历数组。
4. O(n log n)：线性对数时间复杂度，通常出现在快速排序、归并排序等分治算法中。
5. O(n^2)、O(n3)：平方、立方时间复杂度，通常出现在嵌套循环的算法中。

选择合适的算法和数据结构可以使时间复杂度最小化，从而提高算法的执行效率。

时间复杂度能干什么

写代码过程中，就可以大概知道代码运行速度

时间复杂度是一种衡量算法效率的方法，可以用来比较不同算法的运行时间。

通过分析算法的时间复杂度，我们可以：

1. 了解算法在输入规模增大时的运行时间变化情况，从而预测算法的性能表现。
2. 选择最优的算法来解决特定问题，以确保在大规模数据情况下有较高的效率。
3. 进行算法优化和改进，以减少算法的运行时间。

时间复杂度能够帮助我们理解和分析算法的效率，指导我们在编写和选择算法时做出更合理的决策。

时间复杂度表示方法

大写O，出自《解析数论》

大O表示法：使用大O符号来表示算法的时间复杂度。

O表示有很多，例举几个: O(1)、O(n)、O(n^2)、O(log n)…

O(n)表示算法的运行时间与输入规模n成线性关系，O(n^2)表示算法的运行时间与输入规模n的平方成正比。

O(1) 复杂度 – 除了循环和递归意外情形

执行时间不受某个变量(n)影响

// O(1)
const a = 1;
const b = 2;

// 时间复杂度: O（1）

function fun( num ){
   
  return num++;
}

fun(6)
fun(6)
fun(6)
fun(6)
fun(6)
// 时间复杂度: O（1）

O(n) 复杂度 --单层循环/遍历

循环，代码会执行n遍

//0(n)
let n = 100;
for(let i=0;i<n;i++){
   
  console.log( i );
}
// 时间复杂度: O（n）

function fun( n ){
   
  // O(1)
  let i = 1;
  i += 2;

  // O(n)
  for( var k=0;k<n; k++){
   
    console.log( k );
  }
}

fun( 10 );

// 时间复杂度: O(1) + O（n） = O(n)

O(n^2) 复杂度 – 循环嵌套

function foo(){
   
  let arr = [];
  for(let i =0;i<n;i++){
   
    arr.push( [] );
    for(let k =0;k<n;k++){
   
      arr[k].push('a');
    }
  }
}
foo( 10 ); 
// 时间复杂度: O（n）* O（n） = O(n^2)

O(log n) 复杂度

//0(TogN)

let i=1;
const n =6

while( i<n ){
   
  i=i*2;
}
// 时间复杂度: O(log n)

空间复杂度

空间复杂度是什么

执行当前算法需要占用大概多少内存空间

空间复杂度是算法在执行过程中所需的内存空间大小。

时间复杂度表示方法

通常用大O符号来表示，例如O(1)、O(n)、O(n^2)等。

• O(1)表示空间复杂度是常量，与输入规模无关；
• O(n)表示空间复杂度与输入规模成正比；
• O(n^2)表示空间复杂度与输入规模的平方成正比。

在设计算法时，需要考虑空间复杂度，以确保程序在运行时不会占用过多的内存空间。

O(1) 复杂度

let a = 1;
a++

// 空间复杂度: O(1)

O(n) 复杂度 – 循环嵌套

let n = 100; 
let arr = []; 

for(let i=0;i<n;i++){
   
  arr.push(1);
} 

// 空间复杂度: O(n)

O(n^2) 复杂度 – 循环嵌套

let n = 100;
let arr = [];
for(let i=0;i<n;i++){
   
  arr.push([]);
  for(let k=0;k<n;k++){
   
    arr[j].push('');
  }
}
// 空间复杂度: O(n^2)

时间复杂度与空间复杂度

区分与联系

时间复杂度和空间复杂度是分别用来衡量算法 执行时间 和 占用空间 的指标。

它们之间存在联系，但又有一些区别。

时间复杂度 （Time Complexity）衡量的是算法执行所需的时间。它表示随着输入规模的增加，算法执行所需的时间增长的趋势。

通常用大O符号来表示时间复杂度。

时间复杂度描述的是算法的运行时间与输入规模之间的关系。

空间复杂度 （Space Complexity）衡量的是算法在执行过程中所占用的内存空间。

它表示随着输入规模的增加，算法所需的额外空间的增长趋势。

同样，空间复杂度也用大O符号来表示。

区分：

• 时间复杂度关注的是算法的 执行时间，而空间复杂度关注的是算法占用的 内存空间。
• 时间复杂度是对算法运行 时间复杂度 ，而空间复杂度是对算法占用 内存空间的度量。

联系：

• 时间复杂度和空间复杂度都是 度量算法性能 的重要指标，它们都关注算法在 输入规模增大 时的表现。
• 一些算法中，时间复杂度和空间复杂度之间 存在权衡关系。

有些算法可能在时间复杂度较低的情况下，需要占用较高的空间；相反，有些算法可能在空间复杂度较低的情况下，需要更多的执行时间。

归纳： 时间复杂度和空间复杂度是用来评估算法性能的指标，它们分别关注算法的执行时间和占用空间。在设计和分析算法时，我们需要综合考虑这两个指标，以找到最优的解决方案。

衡量标准有什么区别

时间复杂度和空间复杂度作为算法性能的度量指标，有以下区别的衡量标准：

时间复杂度的衡量标准：

执行时间：

时间复杂度主要关注的是算法执行所需的时间。

操作次数：

时间复杂度以算法中的基本操作次数为基础，来描述算法执行的时间增长趋势。

输入规模：

时间复杂度随着输入规模的增加而增加，反映了算法处理更大数据量时所需的时间。

空间复杂度的衡量标准：

内存占用：

空间复杂度主要关注的是算法在执行过程中所占用的内存空间。

额外空间：

空间复杂度是除了输入数据本身之外，算法执行过程中额外所需的空间大小。

输入规模：

空间复杂度通常与输入规模无关，它表示算法执行过程中所需的额外空间随着问题规模增加的趋势。

总结

时间复杂度通过分析算法中的基本操作次数，以及这些操作在不同输入规模下的执行时间，来衡量算法的执行效率。

而空间复杂度则关注算法执行过程中所占用的内存空间大小，衡量算法的内存利用情况。

两者都是评估算法性能的重要指标，但关注的方面不同。

在算法设计和分析中，我们需要综合考虑时间复杂度和空间复杂度，以找到最优的解决方案。

衡量标准举例

下面举例说明时间复杂度和空间复杂度的衡量：

时间复杂度的举例

考虑一个简单的排序算法，如冒泡排序。

在最坏情况下，冒泡排序需要比较n(n-1)/2次，其中n是待排序数据的数量。

因此，冒泡排序的时间复杂度为O(n^2)。

另一个例子是二分查找算法。

在一组有序数据中查找某个值，二分查找的时间复杂度为O(log n)，其中n是数据的数量。

空间复杂度的举例

考虑一个求斐波那契数列的算法。

一个简单的递归实现会占用大量的空间，因为每次调用时都需要存储前面的结果。

例如，计算Fibonacci(5)需要计算Fibonacci(4)和Fibonacci(3)，而计算Fibonacci(4)需要计算Fibonacci(3)和Fibonacci(2)。

递归实现的空间复杂度为O(n)。

相反，迭代实现的空间复杂度为O(1)，因为它只需要存储前两个结果即可计算后续的结果。这种实现方式在处理大规模数据时更加高效。

时间复杂度和空间复杂度是算法性能评估的重要指标。

在算法设计和分析时，需要综合考虑这两个因素，以找到最优的解决方案。

二者举例

时间复杂度的举例：

线性搜索：

假设有一个包含n个元素的数组，我们要在数组中查找一个特定的元素。

在最坏的情况下，即元素不在数组中或者在最后一个位置，线性搜索的时间复杂度为O(n)，因为需要遍历整个数组。

插入排序：

插入排序是一种简单的排序算法。

在最坏的情况下，即待排序的数组是逆序的，插入排序的时间复杂度为O(n^2)。

因为每个元素都需要与已排序部分的元素进行比较和移动。

空间复杂度的举例：

快速排序：

快速排序是一种常用的排序算法，它使用递归实现。

在每次递归调用时，快速排序需要使用额外的堆栈空间来保存函数的调用信息。

在最坏的情况下，即待排序的数组已经是有序的或者逆序的，快速排序的空间复杂度为O(n)，因为递归调用的深度为n。

动态规划：

动态规划是一种解决最优化问题的算法思想。

在动态规划的过程中，通常需要创建一个二维数组或者其他数据结构来保存中间结果。

这些额外的数据结构会占用一定的空间，因此动态规划的空间复杂度可以是O(n^2)或者更高，取决于问题的规模。

需要注意的是，时间复杂度和空间复杂度都是基于算法的输入规模进行分析的，因此在不同的情况下，同一个算法的复杂度可能会有所不同。

以上举例仅用于说明概念，实际应用中需要根据具体情况进行分析和评估。