---
tags: 資芽
title: 手寫作業8
---
# 姓名:李緒成

## 1
### (a) 否, 當$f_{1}(n) = O(n^{3})$, $f_{2}(n) = O(1)$, $f_{3}(n) = O(n)$
### (b) 正確, 可以把$f, g$函數跟$Q$問題的過程直接當成P問題的過程，故P存在一個多項式時間複雜度
### (c\) 否, 當$f=O(n)$, $g=O(n)$, $P=O(n)$ $Q=O(n!)$

## 2

## 3
### 將輸入$(a_1,a_2...a_n)$變成點集$S = (0, a_i), |s|=n$, 則當最近點對答案為$0$時輸出$NO$, 反之答案大於$0$時輸出$YES$

## 4
### 用一個陣列b紀錄, $b_i$紀錄輸入a中有幾個數字為b_i, 執行完後輸出任意一個$i$滿足$b_i > 1$即為答案
* 時間複雜度 $= O(n)$ 空間複雜度 $= O(n)$