COMP1730 Final Exam Submissions

Question 1: Improving code quality (5/40)

An integer $b$ is called a non-trivial divisor of a positive integer $n$ if $b$ is between 2 and $n−1$ such that nn is divisible by $b$, meaning that the remainder of the integer division nn by $b$ is zero. The following correct function takes as input a positive integer, and returns how many non-trivial divisors are there for the given input.

def do_it(xxx):
    tHeReSuLt=0
    u=1
    while u<=xxx//1:
        # check if divides
        if xxx%u==0:
            # exclude some random numbers
            if not(u==1 or u==xxx):
                tHeReSuLt=tHeReSuLt+1
        else:
            pass # do nothing lol
        # increment but not really important
        u=u+1-0
    return int(str(tHeReSuLt))

Describe all distinct ways in which the quality of the code above can be improved without affecting to its functional correctness.

To gain marks, your suggested improvements must be specific. For example, if you think that naming should be improved, you must give at least one specific example of which names should be changed and to what; just answering "better names" is not enough. Do not simply write your suggested improvements as comments inside the function. Writing a new function or rewriting the function is not an acceptable answer, regardless of whether it is correct or not.

Response

fdef f(aAa):
    ReS=0
    i=0
    while i<=len(aAa)-1:
        if aAa[i]%2==0:
            ReS=ReS+1
        else:
            pass
        i=i+1-0
    return int(str(ReS))

def count_adjacent_changes(seq):
    """
    seq 是一个序列（长度可以为 0 或更大）
    返回 seq 中相邻元素不相等的次数
    也就是统计满足 seq[i] != seq[i-1] 的 i 的个数（i 从 1 开始）
    假设元素之间的 != 比较总是有效并返回 True/False
    """

def test_count_adjacent_changes():
    # 1) 空序列：没有相邻元素可比较，所以变化次数为 0
    assert count_adjacent_changes([]) == 0

    # 2) 长度为 1：同样没有相邻对，变化次数为 0
    assert count_adjacent_changes([7]) == 0

    # 3) 全部相同：任意相邻元素都相等，变化次数为 0
    assert count_adjacent_changes([1, 1, 1]) == 0

    # 4) 混合情况：逐对比较
    #    [1, 2, 2, 3, 1]
    #    1!=2 (1), 2==2 (0), 2!=3 (1), 3!=1 (1) => 总计 3
    assert count_adjacent_changes([1, 2, 2, 3, 1]) == 3

def count_with_prefix(strings, prefix):
    """
    strings 是字符串列表
    prefix 是字符串
    返回 strings 中以 prefix 作为开头的字符串数量
    使用 Python 的规则理解“开头”：比如 "abc" 以 "a" 开头，"" 以 "" 开头
    假设参数类型总是有效
    """

def test_count_with_prefix():
    # 1) 空列表：不管前缀是什么，都匹配不到任何字符串
    assert count_with_prefix([], "a") == 0

    # 2) 空前缀：按 Python 规则，所有字符串都以 "" 开头（包括空字符串）
    assert count_with_prefix(["", "a", "ab"], "") == 3

    # 3) 大小写敏感： "Apply" 不是以 "app" 开头
    #    "apple" ✓, "app" ✓, "Apply" ✗, "ap" ✗ => 2
    assert count_with_prefix(["apple", "app", "Apply", "ap"], "app") == 2

    # 4) 正常情况 + 再次验证大小写敏感： "Helo" 不是以 "he" 开头
    #    "hello" ✓, "he" ✓, "hey" ✓, "Helo" ✗ => 3
    assert count_with_prefix(["hello", "he", "hey", "Helo"], "he") == 3

def count_intervals_containing(intervals, x):
    """
    intervals 是一个列表，其中每个元素是 (start, end) 二元组
    并且保证 start <= end
    x 是一个数字
    返回 intervals 中满足 start <= x <= end 的区间个数（两端都算包含）
    假设比较运算总是有效
    """

def test_count_intervals_containing():
    # 1) 空区间列表：没有区间，自然包含数为 0
    assert count_intervals_containing([], 5) == 0

    # 2) 端点包含 + 退化区间：
    #    (1,1) 表示只包含点 1；(0,2) 也包含 1 => 2 个
    assert count_intervals_containing([(1, 1), (0, 2)], 1) == 2

    # 3) 含负数区间 + 跨越 0：
    #    (-3,-1) 包含 -2；(-2,2) 也包含 -2；(3,5) 不包含 => 2 个
    assert count_intervals_containing([(-3, -1), (-2, 2), (3, 5)], -2) == 2

    # 4) 再次验证“端点也算包含”：
    #    x=3 在 (1,3) 的右端点上，算包含；也在 (3,7) 的左端点上，算包含；
    #    (4,6) 不包含 => 2 个
    assert count_intervals_containing([(1, 3), (3, 7), (4, 6)], 3) == 2

Question 2: Testing (5/40)

We want to write tests for a function with signature and docstring defined as follows:

def sequence_dissimilarity(s1, s2)
    """
    s1 and s2 are two sequences of the same length
    Returns the number of i-th elements that are NOT equal
    between two sequences, i.e., where s1[i] != s2[i]
    Assume that this comparison is always valid and evaluates to True or False
    """
def sequence_dissimilarity(s1, s2)
    """
    s1 和 s2 是两个长度相同的序列
    返回两个序列中“对应位置 i 的元素不相等”的位置数量
    也就是统计满足 s1[i] != s2[i] 的 i 的个数
    假设这种比较总是合法的，并且比较结果一定是 True 或 False
    """

Write at most 4 test cases for this function (every test case after the first four will be ignored). For each test case, you must write the inputs (arguments to the function) and the expected return value. You may format your answer in anyway, provided that the inputs and output can be clearly identified. Each test case should specify valid arguments for the function. Your test cases should cover relevant corner cases.

def test_sequence_dissimilarity():
    # 1) 两个空序列（长度为0）
    assert sequence_dissimilarity([], []) == 0

    # 2) 完全相同（无任何不相等）
    assert sequence_dissimilarity([1, 2, 3], [1, 2, 3]) == 0

    # 3) 完全不同（每个位置都不相等）
    assert sequence_dissimilarity("abc", "XYZ") == 3

    # 4) 部分不同 + 混合类型（比较始终合法）
    assert sequence_dissimilarity([1, "2", 3, "x"], [1, 2, 4, "x"]) == 2

Question 3: Debugging (5/40)

The argmin of a sequence is the index (position) of the smallest element in the sequence. For example, if the sequence is [3,4,5], the argmin is 0, because the smallest value is 3 and is at index 0. If the smallest value is not unique, the argmin function can return any index where it appears. For example, if the sequence is [5,5,5], any of the indices 0, 1 or 2 is a valid answer. We assume that the input sequence is non-empty.

Below is an implementation of the argmin function:

def argmin(a):
    a = list(a)
    p = 0
    i = 0
    a.sort()
    for x in a:
        if x < a[p]:
            p = i
        i = i + 1
    return p

However, the function above is not correct:

(a) Provide an example of function call with arguments of correct type that makes this function return an incorrect result. a must be a non-empty sequence of numbers.

(b) Explain the cause of the error that you have found, i.e., what is wrong with this function. Your answer must explain what is wrong with the function as given. Writing a new function or rewriting/fixing the function is not an acceptable answer, regardless of whether it is correct or not.

argmin([2, 1])

argmin([3, 1, 2])

def argmax(a):
    a = list(a)
    p = 0
    i = 0
    a.sort()              # 企图“帮忙”处理，但这里埋雷
    for x in a:
        if x > a[p]:
            p = i
        i = i + 1
    return p

def test_argmax_examples():
    # 单元素：通常会“碰巧正确”
    assert argmax([7]) == 0

    # 严格递增：返回的索引会和原序列索引不一致（提示：这里有坑）
    # 你可以自己打印 argmax([1,2,3]) 看看输出
    _ = argmax([1, 2, 3])

    # 严格递减：同理
    _ = argmax([3, 2, 1])

    # 含重复最大值：允许返回任意一个最大值位置（但必须是原序列的位置！）
    _ = argmax([5, 1, 5, 2])

    # 含负数
    _ = argmax([-10, -3, -7])

    # 非 list 的序列也应支持（例如 tuple）
    _ = argmax((2, 9, 1))

argmax([2, 9, 1])

def first_index_of(s, target):
    i = 0
    for x in s:
        if x == target:
            return i + 1     # <- 这里可能有问题
        i = i + 1
    return -1

def test_first_index_of_examples():
    # 空序列：应返回 -1
    assert first_index_of([], 3) == -1

    # 在开头
    _ = first_index_of([9, 1, 2], 9)

    # 在中间
    _ = first_index_of([9, 1, 2], 1)

    # 在结尾
    _ = first_index_of([9, 1, 2], 2)

    # 不存在
    assert first_index_of([9, 1, 2], 7) == -1

    # 重复元素：必须返回首次出现的索引
    _ = first_index_of([5, 5, 5], 5)

    # 也支持字符串（序列）
    _ = first_index_of("banana", "a")

first_index_of([9, 1, 2], 9)

def count_runs(a):
    if a == []:
        return 0
    count = 0
    prev = a[0]
    for x in a:
        if x != prev:
            count = count + 1
        prev = x
    return count

def test_count_runs_examples():
    # 空序列
    assert count_runs([]) == 0

    # 单元素：应该是 1 段
    _ = count_runs([7])

    # 全相同：应该是 1 段
    _ = count_runs([1, 1, 1, 1])

    # 全不同：每个元素都是一段
    _ = count_runs([1, 2, 3, 4])

    # 有多段
    _ = count_runs([1, 1, 2, 2, 2, 1])

    # 含字符串元素也应可用
    _ = count_runs(["a", "a", "b", "b", "a"])

    # 含 None
    _ = count_runs([None, None, 0, 0, None])

count_runs([7])

Question 4.1: Time complexity (2/40)

Consider the function:

def g(A):
    res = 0.0
    for i in range(A.shape[0]):
        for j in range(i, A.shape[1]):
            res += A[i, j]
    return res

where A is an n by n 2D NumPy array of floating-point numbers (A.shape[0] == A.shape[1] == n).

Write down the time complexity of g(A) in big-O notation as a function of n . Explain the reason why, e.g., by analysing the code line by line and summarising it**.** Correct time complexity without sufficient explanation and reasoning will receive zero marks.

def g(A):
    res = 0.0
    for i in range(A.shape[0]):
        for j in range(i, A.shape[1]):
            res += A[i, j]
    return res

时间复杂度汇总

1. 时间复杂度怎么判断（核心规则）

把程序想象成：输入规模为 n 时，会执行多少次“基本操作”（比较、加减、赋值、访问数组等）。

• 忽略常数：3n + 20 记为 O(n)
• 只看最高阶：n^2 + n 记为 O(n^2)
• 顺序相加：先做 A 再做 B → O(A + B)
• 嵌套相乘：外层 n 次、内层 n 次 → O(n * n) = O(n^2)
• 每次规模减半：n → n/2 → n/4 ... 是 O(log n)
• 分支暴增（枚举子集/排列）通常是指数级或阶乘级

2. O(1) 常数时间

特点：执行次数不随 n 变。

代码示例：数组索引访问

def get_middle(a):
    return a[len(a)//2]  # 访问一次

为什么是 O(1)：无论 a 多长，都只做固定次数操作（求长度、除法、一次索引）。

典型：取数组某个位置、交换两个变量、栈/队列的 push/pop（在实现良好时）。

3. O(log n) 对数时间

特点：每一步把问题规模“砍半/按比例缩小”。

代码示例：二分查找

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

为什么是 O(log n)：每次循环把区间缩小一半：n → n/2 → n/4 → ... → 1 需要的步数是 log2(n) 级别。

4. O(√n)（很常见但容易忽略）

特点：循环到 sqrt(n) 就能解决（常见于数论）。

代码示例：判断是否有非平凡因子（试除到 √n）

def has_divisor(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return True
        i += 1
    return False

为什么是 O(√n)：i*i <= n ⇒ i <= √n，最多尝试约 √n 次。

4. O(n) 线性时间

特点：把输入完整扫一遍。

代码示例：线性查找

def linear_search(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

为什么是 O(n)：最坏情况下要检查 n 个元素。

注意：有些操作“看起来一行”，但可能是 O(n)，例如 Python 的 x in list、list.count、list.remove 等都要线性扫描。

5. O(n + m)（两个规模相加）

特点：分别扫两份数据，各扫一遍。

代码示例：合并两个数组（不排序）

def concat(a, b):
    res = []
    for x in a:
        res.append(x)
    for y in b:
        res.append(y)
    return res

为什么是 O(n + m)：第一段做 n 次，第二段做 m 次，总计相加。

图算法里常见 O(V + E)（点+边），也是同理。

6. O(n log n)（最常见的“高效排序/分治”复杂度）

特点：通常是 分治：分成若干份（log 层），每层做 O(n) 工作。

代码示例：归并排序（经典）

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    i = j = 0
    res = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

为什么是 O(n log n)：

• 分裂次数：n → n/2 → ... 有 log n 层
• 每一层合并总工作量：把所有元素合并一遍，总计 O(n)
• 所以总计：O(n) * O(log n) = O(n log n)

现实中：大多数比较排序在平均/最坏可做到 O(n log n)（归并、堆排序），快速排序平均 O(n log n) 但最坏 O(n^2)。

7. O(n²) 二次时间（双重循环/两两比较）

特点：所有“成对组合”类问题很容易出现。

代码示例：统计所有配对 (i, j)

def count_pairs(a):
    n = len(a)
    c = 0
    for i in range(n):
        for j in range(n):
            c += 1
    return c

为什么是 O(n²)：外层 n 次，内层 n 次，总 n*n。

更真实一点：两两比较是否相等

def has_duplicate_slow(a):
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] == a[j]:
                return True
    return False

这里比较次数约为 n(n-1)/2，仍是 O(n²)（忽略常数 1/2）。

8. O(n³) 三次时间（3 层嵌套/某些 DP）

代码示例：三重循环

def triple_work(n):
    c = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c += 1
    return c

为什么是 O(n³)：n * n * n。

典型：Floyd-Warshall 全源最短路就是 O(n³)（n 个点）。

9. O(2^n) 指数时间（枚举所有子集 / 爆炸）

代码示例：生成所有子集

def all_subsets(a):
    n = len(a)
    res = []
    for mask in range(1 << n):      # 2^n 个 mask
        subset = []
        for i in range(n):          # 每个 mask 扫 n 位
            if mask & (1 << i):
                subset.append(a[i])
        res.append(subset)
    return res

复杂度：严格说是 O(n * 2^n)（因为每个子集构造要扫 n 位）。

为什么会爆炸：子集数量本身就是 2^n，规模增长极快。

10. O(n!) 阶乘时间（排列）

代码示例：生成全排列（回溯）

def permutations(a):
    res = []
    used = [False] * len(a)
    path = []

    def dfs():
        if len(path) == len(a):
            res.append(path.copy())
            return
        for i in range(len(a)):
            if not used[i]:
                used[i] = True
                path.append(a[i])
                dfs()
                path.pop()
                used[i] = False

    dfs()
    return res

为什么是 O(n!)：第 1 位有 n 种选法，第 2 位 n-1 … ⇒ n*(n-1)*...*1 = n!。

11. 递归复杂度的两个典型模板（看一眼就会用）

A. “每次减半”的递归：O(log n)

def rec_half(n):
    if n <= 1:
        return 1
    return rec_half(n // 2) + 1

每次 n → n/2，递归层数 log n。

B. 经典斐波那契（错误示范）：O(2^n)

def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n-1) + fib_slow(n-2)

递归树分叉，节点数指数级增长（重复计算大量子问题）。

12. 常见“陷阱”：看起来是 O(n)，其实是 O(n²)

代码示例：循环里用了 .count()（每次 O(n)）

def count_freq_bad(a):
    freq = {}
    for x in a:
        freq[x] = a.count(x)   # count 是 O(n)，外层又 n 次 => O(n^2)
    return freq

为什么是 O(n²)：外层 n 次，每次 count 扫 n ⇒ n*n。

✅ 改成真正 O(n)：

def count_freq_good(a):
    freq = {}
    for x in a:
        freq[x] = freq.get(x, 0) + 1
    return freq

13. 一张“常见复杂度-典型原因”速查

• O(1)：固定次数操作
• O(log n)：每轮规模按比例缩小（/2、/3…）
• O(√n)：循环到平方根（试除、某些优化）
• O(n)：扫一遍输入
• O(n + m)：扫两份输入
• O(n log n)：分治（log 层 × 每层 O(n)）
• O(n²)：两两组合/双重循环
• O(n³)：三重循环/某些全局 DP
• O(2^n)：枚举子集/指数分叉递归
• O(n!)：枚举排列

表 1：常见时间复杂度（带代码结构 + 原因推导）

记 n 为输入规模（如列表长度），m 为另一份输入规模（如第二个列表长度），V/E 为图的点/边数。

表 2：Python 常见操作的时间复杂度速查（很实用）

这里默认 平均情况（哈希结构会注明“平均/极端”）。n 是容器大小。

公众号：AI悦创【二维码】