c - 算法分析 -- Big O Notation

Question

什么是确定数据结构和算法的运行时间(大 O 表示法)的好策略。我有以下内容来计算运行时间并且我有 麻烦确定它会是什么。

AINC 是一个数组，其中包含 n 个按升序排列的整数。

AD 是一个包含 n 个整数的数组，按降序排列。

AR 是一个数组，包含 n 个随机顺序的整数。

Q 是一个以链表形式实现并包含 p 个元素的队列。

LINK是一个包含n个节点的链表。

CIRC是一个包含n个元素的循环链表，其中C指向最后一个元素。

T 是一棵包含 n 个节点的二叉搜索树。

a) 使用线性搜索在 AINC 中搜索元素。

b) 删除链表LINK的第10个节点。

c) 调用一个使用 Q 的函数，并调用 dequeue m 次。

d) 在列表 CIRC 的末尾插入一个元素。

e) 删除 CIRC 的最后一个元素。

f) 寻找 T 的最大元素。

g) 确定 T 的高度。

h) 调用 selectionsort (AINC, n)。

i) 一个接一个地打两个电话。第一个调用是 mergesort(AD,n)，然后是调用 insertionsort(AD,n)。

j) 将十进制整数 num 转换为其等效的二进制。

***这不是硬件。我正在准备考试。

Answer 1

(因为OP要求它)

你拿起一张纸。

• 如果您的问题提到了一个数字(例如，重复 n 次，或找到第 n 个最后一个元素):

当数字为 1(如果适用)时，您可以在纸上手动执行执行上述操作所需的操作。

您重复该数字的以下每个值:2、10、20、100、1000 和 10000。为了好玩，您也可以尝试使用问题中提到的实际数字。

您测量每个案例花费的时间，然后在一张纸上绘制(哦，电子表格也可以，我想)函数 t(n)，其中 t 是时间，n 是数字。

您翻阅旧数学书来识别曲线。例如。如果它是抛物线，那么您很可能已经掌握了 O(n^2) 算法。

• 如果您的问题没有提到数字:

通过在任何提到的数据结构(数组、列表等)中使用 2、10、20、100、1000 和 10000 个元素，重复上述过程。如果“结构”是一个数字，就使用那么多数字。

注意:

如果您设法将上述过程可视化，没有将这个星球上剩余的一半树木变成纸，也没有让您的手掉下来，那么您就已经接近半正经的直觉技术了。

不过，您应该阅读正确的数学方法来处理这个问题 - 在这种情况下，直觉只能带您走这么远。

此外，您提到的大多数示例都非常基础，以至于大多数人只是记住(稍后他们才知道)它们的复杂性。你真的应该得到一本书或一些像样的笔记。 Introduction to Algorithms是本领域的一本不错的厚厚介绍性书。

编辑:

在 Google 中搜索算法和复杂性 也会产生一大堆有趣的结果。你应该偶尔尝试一下......