DSA Big O

大o符号演习

关键概念

• 空间复杂性是指算法需要完成的物理内存量。
• 时间复杂性是指算法需要完成的操作数量。
• 大o符号是描述算法的时间复杂性的一种方式。
• 线性关系是在两种不同的事物（例如操作和循环）直接生长，彼此成比例的。
• 无论输入多大，恒定时间（O（1））需要相同的时间来完成。 “圣杯”。
• 对数时间（O（log（n）））在较大的输入中需要更长的时间，但是运行时间却缓慢增加。将问题大小切成一半。恒定时间之后的下一个最好的事情（o（1））。
• 线性时间（O（n））的运行时间与输入的大小（n）直接成正比。
• 多项式时间（O（n^k））的运行时间将是一些输入大小n升高到某个恒定功率k 。
• 指数时间（O（2^n））的运行时间随着输入大小的任何增加而迅速增长。

例子

• O（1） - O（1）算法的示例正在访问数组项目或执行基本算术操作（例如，添加2个数字）。

• o（log（n）） - A（O（log（log（n）））算法的一个很好的例子正在电话簿中查找人员。您无需检查电话簿中的每个人即可找到合适的书。取而代之的是，您可以通过基于其名称在字母顺序的位置进行查找，而在每个部分中，您只需要探索每个部分的子集，然后才能最终找到某人的电话号码。当然，更大的电话簿仍然会花费您更长的时间，但是它不会像额外尺寸的比例增加那样快地增长。请记住：
  • 选择执行某些动作的下一个元素是几种可能性之一
  • 只需要选择一个。或者
  • 执行动作的元素是N的数字

• o（n） - O（n）算法的一些示例是将数组中的元素求和，并在数组中找到最小或最大值。

• o（n^k） - 理解多项式时间复杂性的最简单方法是嵌套环。需要在输入上进行2个循环的算法是O（n^2），而需要3个循环的算法为O（n^3）。在这两种情况下，我们都有多项式时间的复杂性。

• o（2^n） - 对于大小2的输入，指数时间算法将需要2^2 = 4时间。对于大小10的输入，相同的算法将需要2^10 = 1024时间，并且输入尺寸为100，则需要2^100 = 1.26765060022823 * 1030时间。运行时间O（2^n）的算法通常是递归算法，可以通过递归解决两个尺寸N-1的较小问题来解决尺寸N的问题。

时间复杂度图

不同时间复杂性要求的操作

资源

• Cheetsheet
• Web Dev简化
• CS50计算复杂性视频
• hackerrank大o符号视频

演习概述

在这些练习中，您将练习确定算法的大复杂性。对于每个钻头，我们将提供一个具有功能的代码段，您将通过分析代码而无需运行代码来确定大量的复杂性。

1。这是多少？

1. 确定以下算法的大O：您坐在有15个人的房间里。您想为您的狗找到一个玩伴，最好是同一品种。因此，您想知道15个人中的任何人是否与您的狗具有相同的品种。您站起来大喊大叫，在这里有一个金毛猎犬，想成为我的金色的比赛日期。有人大喊大叫 - “我愿意，很乐意把他带走”

2. 确定以下算法的大O：您坐在有15个人的房间里。您想找到一个同一品种的狗的玩伴。因此，您想知道15个人中的任何人是否与您的狗具有相同的品种。您从第一人称开始，问他是否有金毛寻回犬。他说不，然后您问下一个人和下一个人，下一个人，直到找到一个有金色或没有其他人要问的人。

2。甚至奇怪

以下算法的大O是什么？解释您的答案

    if (value % 2 === 0) {
        return true;
    }
    else {
        return false;
    }
}

3。你在这里吗？

以下算法的大O是什么？解释您的答案

    for (let i = 0; i < arr1.length; i++) {
        const el1 = arr1[i];
        for (let j = 0; j < arr2.length; j++) {
            const el2 = arr2[j];
            if (el1 === el2) return true;
        }
    }
    return false;
}

4。倍增

以下算法的大O是什么？解释您的答案

    for (let i = 0; i < array.length; i++) {
        array[i] *= 2;
    }
    return array;
}

5。幼稚搜索

以下算法的大O是什么？解释您的答案

    for (let i = 0; i < array.length; i++) {
        if (array[i] === item) {
            return i;
        }
    }
}

6。创建对

以下算法的大O是什么？解释您的答案

    for (let i = 0; i < arr.length; i++) {
        for(let j = i + 1; j < arr.length; j++) {
            console.log(arr[i] + ", " +  arr[j] );
        }
    }
}

7。计算序列

以下算法有什么作用？它的运行时复杂性是什么？解释您的答案

    let result = [];
    for (let i = 1; i <= num; i++) {

        if (i === 1) {
            result.push(0);
        }
        else if (i === 2) {
            result.push(1);
        }
        else {
            result.push(result[i - 2] + result[i - 3]);
        }
    }
    return result;
}

8。有效的搜索

在此示例中，我们回到了使用更复杂的方法搜索的问题，而不是在上面的幼稚搜索中。假设输入阵列始终是分类的。以下算法的大O是什么？解释您的答案

    let minIndex = 0;
    let maxIndex = array.length - 1;
    let currentIndex;
    let currentElement;

    while (minIndex <= maxIndex) {
        currentIndex = Math.floor((minIndex + maxIndex) / 2);
        currentElement = array[currentIndex];

        if (currentElement < item) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > item) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }
    return -1;
}

9。随机元素

以下算法的大O是什么？解释您的答案

    return arr[Math.floor(Math.random() * arr.length)];
}

10。我是什么？

以下算法有什么作用？以下算法的大O是什么？解释您的答案

    if (n < 2 || n % 1 !== 0) {
        return false;
    }
    for (let i = 2; i < n; ++i) {
        if (n % i === 0) return false;
    }
    return true;
}

11。河内塔

河内塔是一个非常著名的数学难题（有些人称之为游戏！）。这就是这样：

• 有三个杆和许多不同尺寸的磁盘可以滑到任何杆上。拼图始于磁盘在一根杆上以尺寸上升顺序整齐地堆叠起来，这是顶部最小的磁盘（形成圆锥形）。另外两个杆一开始是空的。

• 难题的目的是将整个杆堆移到另一根杆（不能是以前被堆叠的原始杆），也将其沿着上升顺序堆叠。遵守以下规则应该做到这一点：

  • 一次只能移动一个磁盘
  • 每个举动都包括从一个杆上取上上盘并将其滑到另一个杆上，在该杆上可能已经存在的另一个磁盘上。
  • 较大的磁盘可能不会放在较小的磁盘上。

您的任务：

• 得出一种算法来解决河内难题的塔。
• 使用递归实现算法。您的程序应显示磁盘从一根杆到另一杆的每个运动。
• 如果给您5个磁盘，在7个递归电话后，杆的样子如何？
• 用3个磁盘完成难题需要多少个动作？有4个磁盘？有5个磁盘？
• 您的算法的运行时间是多少？

12。迭代版本

迭代而不是递归解决钻头文件12。

13递归大O

从此存储库中获取解决方案，并确定每个回购的时间复杂性（大O）。

14。迭代大o

从JS文件12中的迭代练习中获取解决方案，并确定每个练习的时间复杂性（大O）。