2.10. 练习

2.10. Exercises

中文英文

1. 以下代码片段的 Big O 性能是多少？

   for i in range(n):
       for j in range(n):
           k = 2 + 2
   

   Big O 性能： \(O(n^2)\)

   解释： 有两个嵌套的循环，每个循环运行 \(n\) 次，因此总操作次数为 \(n \times n = n^2\)。

2. 以下代码片段的 Big O 性能是多少？

       for i in range(n):
               k = 2 + 2
   

   Big O 性能： \(O(n)\)

   解释： 有一个循环运行 \(n\) 次，因此操作次数与 \(n\) 成线性关系。

3. 以下代码片段的 Big O 性能是多少？

       i = n
       while i > 0:
           k = 2 + 2
           i = i // 2
   

   Big O 性能： \(O(\log n)\)

   解释： 每次迭代时 \(i\) 的值被减半，因此迭代次数与 \(n\) 可以被 2 除的次数成正比，即 \(\log n\)。

4. 以下代码片段的 Big O 性能是多少？

       for i in range(n):
           for j in range(n):
               for k in range(n):
                   k = 2 + 2
   

   Big O 性能： \(O(n^3)\)

   解释： 有三个嵌套的循环，每个循环运行 \(n\) 次，总操作次数为 \(n \times n \times n = n^3\)。

5. 以下代码片段的 Big O 性能是多少？

       for i in range(n):
           k = 2 + 2
       for j in range(n):
           k = 2 + 2
       for k in range(n):
           k = 2 + 2
   

   Big O 性能： \(O(n)\)

   解释： 虽然有三个分开的循环，但它们是顺序执行的而不是嵌套的。每个循环运行 \(n\) 次，因此总操作次数为 \(3n\)，在 Big O 记法中常数系数被省略，所以为 \(O(n)\)。

6. 设计一个实验来验证 list index 操作符的性能是 \(O(1)\)：

   实验： 测量访问列表中某个特定索引的时间，并对不同大小的列表进行测试。

   实现：

   import timeit
   
   def index_test(n):
       l = list(range(n))
       for _ in range(1000):  # 重复以获得稳定的测量结果
           _ = l[n // 2]  # 访问中间元素
   
   for size in [10, 100, 1000, 10000]:
       time_taken = timeit.timeit(lambda: index_test(size), number=1)
       print(f"列表大小: {size}, 耗时: {time_taken:.6f} 秒")
   

   预期结果： 无论列表大小如何，时间应该保持不变，从而验证 \(O(1)\) 性能。

7. 设计一个实验来验证 get item 和 set item 操作在字典中的性能是 \(O(1)\)：

   实验： 测量从字典中获取和设置项的时间，并对不同大小的字典进行测试。

   实现：

   import timeit
   
   def dict_get_set_test(n):
       d = {i: i for i in range(n)}
       for _ in range(1000):  # 重复以获得稳定的测量结果
           _ = d[n // 2]  # 获取项
           d[n // 2] = n // 2  # 设置项
   
   for size in [10, 100, 1000, 10000]:
       time_taken = timeit.timeit(lambda: dict_get_set_test(size), number=1)
       print(f"字典大小: {size}, 耗时: {time_taken:.6f} 秒")
   

   预期结果： 无论字典大小如何，时间应该保持不变，从而验证 \(O(1)\) 性能。

8. 设计一个实验来比较 del 操作符在列表和字典中的性能：

   实验： 测量从列表和字典中删除项的时间，并对不同大小的列表和字典进行测试。

   实现：

   import timeit
   
   def list_del_test(n):
       l = list(range(n))
       for _ in range(1000):  # 重复以获得稳定的测量结果
           l.pop()  # 从末尾删除
   
   def dict_del_test(n):
       d = {i: i for i in range(n)}
       for _ in range(1000):  # 重复以获得稳定的测量结果
           del d[n // 2]  # 删除特定键
   
   for size in [10, 100, 1000, 10000]:
       list_time = timeit.timeit(lambda: list_del_test(size), number=1)
       dict_time = timeit.timeit(lambda: dict_del_test(size), number=1)
       print(f"大小: {size}, 列表删除时间: {list_time:.6f} 秒, 字典删除时间: {dict_time:.6f} 秒")
   

   预期结果： 删除字典中的项时间应该保持不变，而从列表中删除项的时间会随着列表大小的增加而线性增长。

9. 给定一个随机顺序的数字列表，编写一个 \(O(n \log n)\) 时间复杂度的算法来找到列表中的第 \(k\) 小的数字：

   算法： 对列表进行排序，然后访问第 \(k\) 小的元素。

   实现：

   def kth_smallest(arr, k):
       sorted_arr = sorted(arr)  # O(n log n) 排序
       return sorted_arr[k - 1]  # 访问第 k 小的元素
   
   # 示例用法：
   import random
   nums = random.sample(range(1, 10000), 5000)  # 生成随机数列表
   print(kth_smallest(nums, 10))
   

10. 能否将上一个问题中的算法改进为线性时间复杂度？解释：

    算法： 使用 Quickselect 算法，这可以在期望的 \(O(n)\) 时间复杂度内找到第 \(k\) 小的元素。

    解释： Quickselect 是一个选择算法，用于在无序列表中找到第 \(k\) 小的元素。它与快速排序算法相关，但仅对列表进行部分排序。其平均时间复杂度为 \(O(n)\)，尽管最坏情况下的复杂度为 \(O(n^2)\)，可以通过使用随机化或中位数的中位数技术来缓解。

    实现：

    import random
    
    def partition(arr, low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
    
    def quickselect(arr, low, high, k):
        if low == high:
            return arr[low]
        pivot_index = random.randint(low, high)
        pivot_index = partition(arr, low, high)
        if k == pivot_index:
            return arr[k]
        elif k < pivot_index:
            return quickselect(arr, low, pivot_index - 1, k)
        else:
            return quickselect(arr, pivot_index + 1, high, k)
    
    def find_kth_smallest(arr, k):
        return quickselect(arr, 0, len(arr) - 1, k - 1)
    
    # 示例用法：
    nums = random.sample(range(1, 10000), 5000)
    print(find_kth_smallest(nums, 10))
    

    解释： Quickselect 算法旨在以平均 \(O(n)\) 时间复杂度找到第 \(k\) 小的元素，使其比排序更高效，只需找到一个元素。

1. Give the Big O performance of the following code fragment:

   for i in range(n):
       for j in range(n):
           k = 2 + 2
   

2. Give the Big O performance of the following code fragment:

       for i in range(n):
               k = 2 + 2
   

3. Give the Big O performance of the following code fragment:

       i = n
       while i > 0:
           k = 2 + 2
           i = i // 2
   

4. Give the Big O performance of the following code fragment:

       for i in range(n):
           for j in range(n):
               for k in range(n):
                   k = 2 + 2
   

5. Give the Big O performance of the following code fragment:

       for i in range(n):
           k = 2 + 2
       for j in range(n):
           k = 2 + 2
       for k in range(n):
           k = 2 + 2
   

6. Devise an experiment to verify that the list index operator is \(O(1)\).

7. Devise an experiment to verify that get item and set item are \(O(1)\) for dictionaries.

8. Devise an experiment that compares the performance of the del operator on lists and dictionaries.

9. Given a list of numbers in random order, write an algorithm that works in \(O(n\log(n))\) to find the \(k\) th smallest number in the list.

10. Can you improve the algorithm from the previous problem to be linear? Explain.

---

最后更新: 2024年9月12日
创建日期: 2024年9月9日