Chapter 3 程 式 問 題 的 應 對 方 法 流 程 實 際 情 況 問 題 使 用 哪 種 程 式 語 言 互 動 是 關 鍵 解 決 問 題 基 本 步 驟 當 你 碰 到 瓶 頸 時 分 析 你 的 答 案 分 析 兩 個 範 例 Big-O 分 析 如 何 運 作 最 佳 平 均 最 壞 情 況 如 何 進 行 Big-O 分 析 最 佳 化 與 Big-O 分 析 總 結
20 恭 喜 你 錄 取 了! 程 式 設 計 師 如 何 贏 在 面 試 面 試 時 最 重 要 的 部 分 無 庸 置 疑 就 是 程 式 設 計 的 面 試 題! 而 這 類 的 題 目 更 是 面 試 者 必 須 藉 此 證 明 自 己 能 力 與 工 作 內 容 相 符 的 機 會! 大 部 分 的 電 腦 與 軟 體 公 司 在 挑 選 雇 用 者 時, 這 部 分 表 現 更 是 佔 有 相 當 大 的 比 重 由 於 許 多 公 司 只 會 從 來 面 試 的 人 當 中 挑 出 約 百 分 之 十 給 予 職 位, 因 此 面 試 題 目 必 須 有 相 當 的 鑑 別 度 當 大 部 分 的 人 都 能 很 快 的 回 答 某 個 題 目 時, 這 樣 的 題 目 便 被 視 為 太 過 簡 單 而 無 法 鑑 別 面 試 者 的 程 度, 所 以 它 就 會 被 換 掉 此 外, 有 些 問 題 更 被 設 計 成 需 花 費 一 小 時 左 右 來 解 決, 所 以 不 要 因 看 到 題 目 時 沒 辦 法 馬 上 想 出 解 法 就 沮 喪, 其 實 大 部 分 的 人 都 沒 辦 法! 這 些 問 題 很 困 難! 有 些 問 題 是 專 門 用 來 觀 察 面 試 者 如 何 處 理 無 法 馬 上 看 出 解 決 方 法 的 難 題! 流 程 程 式 設 計 的 面 試 題 有 一 個 最 重 要 的 目 的, 便 是 觀 察 你 寫 程 式 的 功 力 這 是 面 試 中 最 重 要 的 部 分, 因 為 你 的 回 答 將 決 定 面 試 官 是 否 會 推 薦 錄 用 你 實 際 情 況 你 通 常 會 與 面 試 官 一 對 一 的 面 試 他 會 給 你 筆 與 紙 或 者 白 板, 並 請 你 在 上 面 撰 寫 一 些 程 式 在 寫 程 式 前, 面 試 官 可 能 會 跟 你 討 論 一 下 題 目, 藉 此 觀 察 你 的 思 考 方 式 一 般 來 說, 你 會 被 要 求 寫 一 個 函 式 (function) 或 方 法 (method), 但 有 時 你 需 要 寫 一 個 類 別 的 定 義 或 一 連 串 相 關 的 程 式 碼 模 組 但 無 論 如 何 都 一 定 需 要 寫 程 式, 不 管 是 真 正 的 程 式 或 者 虛 擬 程 式 碼 (pseudo-code) 問 題 面 試 官 所 問 的 題 目 有 一 些 特 別 的 需 求 它 們 必 須 短 到 足 以 在 合 理 的 時 間 內 解 釋 完 畢 與 回 答, 但 卻 又 必 須 複 雜 到 有 一 定 的 鑑 別 度 因 此, 你 不 太 可 能 會 被 問 到 真 實 世 界 的 問 題, 因 為 大 部 分 這 類 的 問 題 都 需 要 花 很 長 時 間 來 解 釋, 更 遑 論 解 決 它 所 花 的 時 間 所 以 這 樣 的 問 題 並 不 適 合 當 成 面 試 題 目 反 之, 許 多 面 試 題 都 需 要 一 些 技 巧 或 是 程 式 語 言 中 不 常 用 的 部 分 面 試 題 往 往 禁 止 你 使 用 最 常 見 的 方 法 或 使 用 理 想 的 資 料 結 構 例 如, 你 可 能 被 問 到 這 樣 的 問 題 : 請 寫 出 一 個 函 式 來 判 定 兩 個 整 數 是 否 相 等, 但 不 能 使 用 任 何 比 較 運 算 子
第 三 章 程 式 問 題 的 應 對 方 法 21 事 實 上, 這 問 題 極 為 愚 蠢 因 為 幾 乎 所 有 的 程 式 語 言 都 有 些 方 法 可 以 迅 速 的 比 較 兩 個 整 數 但 是 你 不 能 回 答 : 這 個 問 題 很 奇 怪, 我 一 直 以 來 都 使 用 相 等 運 算 子 來 實 作, 因 此 我 從 來 沒 有 想 過 這 個 問 題 如 果 你 這 樣 回 答, 你 就 出 局 了! 面 試 官 正 是 要 你 提 出 不 同 的 方 式 來 比 較 兩 個 整 數!( 提 示 : 試 著 用 位 元 運 算 子 ) 你 該 做 的 是 告 訴 面 試 官 你 雖 然 知 道 更 好 的 解 決 方 向, 但 是 你 也 會 照 著 他 所 限 制 的 範 圍 去 提 出 另 一 個 解 答! 例 如, 你 被 要 求 用 雜 湊 表 (hash table) 解 決 某 一 問 題, 你 可 能 會 說 : 如 果 使 用 二 元 搜 尋 樹 會 更 加 簡 單, 因 為 它 更 容 易 取 出 最 大 值, 但 我 們 可 以 試 試 看 如 何 使 用 雜 湊 表 來 解 決 這 個 問 題 許 多 問 題 看 起 來 很 愚 蠢 且 做 作, 有 著 荒 謬 的 限 制, 並 且 使 用 程 式 語 言 中 少 見 的 功 能 然 而 這 就 是 遊 戲 規 則 現 實 世 界 中 的 程 式 設 計 是 無 法 獨 立 進 行 的 在 某 些 特 殊 限 制 下 的 工 作 能 力 是 程 式 開 發 的 一 項 重 要 技 能 當 你 正 確 回 答 的 題 目 越 來 越 多 時, 可 以 猜 想 面 試 官 們 會 越 來 越 難 問 下 去, 因 此 面 試 的 問 題 通 常 只 會 越 來 越 困 難 有 時, 不 同 的 面 試 官 們 會 相 互 討 論, 以 了 解 彼 此 所 提 出 的 問 題 與 你 的 回 答 內 容, 並 藉 此 來 想 接 下 來 的 面 試 題 目 如 果 在 前 幾 關 中, 你 回 答 了 所 有 問 題, 卻 發 現 自 己 在 這 裡 被 難 題 考 倒, 不 用 著 急, 這 可 能 表 示 之 前 的 面 試 官 對 你 的 回 答 印 象 深 刻 呢! 使 用 哪 種 程 式 語 言 如 果 應 徵 的 工 作 需 要 特 定 的 程 式 語 言, 那 你 應 該 知 道 如 何 使 用 它 們, 並 在 面 試 時 正 確 地 用 來 解 決 題 目 如 果 應 徵 的 職 位 並 無 限 定 語 言, 而 且 是 一 般 程 式 開 發 的 職 務, 對 於 主 流 語 言 ( 如 C# Java C++) 的 全 面 了 解 便 以 足 夠, 但 熟 悉 C 語 言 在 許 多 情 況 下 更 是 相 當 吃 香 面 試 官 可 能 會 允 許 你 使 用 其 他 流 行 的 語 言, 如 JavaScript PHP 或 Perl 如 果 可 以 選 擇, 請 選 擇 你 最 熟 悉 的 語 言, 但 仍 要 預 先 想 到 一 些 特 別 的 問 題 需 要 使 用 特 定 的 語 言 來 解 決 此 外, 面 試 官 可 能 不 太 喜 歡 你 使 用 一 些 非 主 流 的 語 言, 例 如 Lisp Python TCL Prolog COBOL 或 Fortran, 但 是 如 果 你 精 通 這 些 語 言, 提 出 要 求 也 無 傷 大 雅 在 去 面 試 之 前, 請 確 保 你 對 於 打 算 在 面 試 時 用 的 語 言 的 語 法 與 用 法 瞭 若 指 掌 如 果 你 打 算 使 用 C++, 卻 發 現 距 離 你 上 次 寫 C++ 的 程 式 已 經 過 了 好 幾 年, 那 你 至 少 應 該 翻 閱 一 本 好 的 C++ 參 考 書 並 重 新 的 熟 悉 它 在 語 言 的 選 擇 上, 最 後 有 件 事 情 需 要 好 好 注 意 : 許 多 人 認 為 Visual Basic 很 少 人 使 用 先 不 管 這 意 見 是 否 正 確, 建 議 你 除 非 應 徵 的 工 作 需 要 使 用 它, 否 則 盡 量 避 免 在 面 試 時 使 用 不 過 你 應 該 要 多 了 解 當 前 程 式 語 言 的 趨 勢 例 如 在 幾 年 前,JavaScript 也 曾 被 視 為 小 眾, 然 而 將 AJAX(Asynchronous JavaScript and XML 的 縮 寫 ) 作 為 核
22 恭 喜 你 錄 取 了! 程 式 設 計 師 如 何 贏 在 面 試 心 技 術 以 開 發 基 於 瀏 覽 器 的 互 動 式 應 用 程 式 的 興 起 改 變 了 業 界 對 於 JavaScript 的 見 解 所 以 說, 世 事 多 變 化! 互 動 是 關 鍵 面 試 時 你 寫 的 程 式 碼 是 面 試 官 唯 一 能 看 到 的 你 的 程 式 如 果 你 寫 出 很 爛 的 程 式, 面 試 官 會 認 為 你 平 常 寫 的 程 式 就 是 這 麼 差 勁 要 記 住, 這 是 你 唯 一 的 機 會 向 面 試 官 展 現 你 的 程 式 功 力, 請 花 一 點 時 間 讓 你 所 寫 出 的 程 式 碼 品 質 穩 定 又 漂 亮 重 新 複 習 你 所 預 計 要 使 用 的 程 式 語 言, 並 寫 出 最 好 的 程 式 碼 程 式 設 計 問 題 的 目 的 是 看 出 面 試 者 如 何 寫 程 式 與 如 何 解 決 問 題 如 果 面 試 官 只 是 想 了 解 你 的 程 式 功 力, 他 大 可 像 程 式 設 計 比 賽 般 給 你 幾 張 考 試 卷 與 答 案 卷, 然 後 一 小 時 後 再 回 來 看 你 的 解 答 因 此 你 必 須 了 解 一 件 事, 除 了 程 式 功 力 外, 面 試 官 最 想 知 道 的 是 你 解 決 問 題 時 的 思 考 過 程 當 你 遇 到 困 難 時, 面 試 官 通 常 會 給 予 一 些 提 示 來 引 導 你 因 此 在 解 決 問 題 的 過 程 中, 盡 量 保 持 與 面 試 官 頻 繁 的 互 動 當 然, 如 果 你 需 要 的 幫 助 越 少, 你 得 到 的 評 價 會 越 高 然 而, 對 於 面 試 官 所 給 的 提 示 若 能 給 予 適 當 的 反 應 並 表 現 出 有 組 織 且 聰 穎 的 思 考 過 程 也 能 大 大 提 升 你 的 評 價! 如 果 你 早 就 知 道 題 目 的 答 案, 不 要 只 是 將 它 脫 口 而 出 試 著 將 答 案 分 解 成 幾 個 獨 立 的 步 驟 並 解 釋 每 一 步 背 後 的 思 考 流 程 這 用 意 是 要 告 知 面 試 官, 你 相 當 了 解 基 本 概 念, 而 不 只 是 成 功 地 背 出 題 目 的 答 案 如 果 你 知 道 任 何 與 這 問 題 相 關 的 資 訊, 即 使 它 並 不 直 接 適 用 於 這 道 問 題, 在 回 答 過 程 中, 你 依 然 可 稍 微 提 到 它 以 顯 示 你 的 廣 泛 知 識 這 樣 一 來, 顯 示 出 你 不 只 是 熱 衷 於 程 式 設 計 的 人, 更 證 明 你 的 邏 輯 思 考 過 程 與 對 電 腦 理 論 的 廣 泛 知 識 此 外, 更 能 讓 面 試 官 覺 得 你 有 著 良 好 的 溝 通 能 力 一 直 保 持 著 互 動 與 討 論! 盡 量 試 著 解 釋 自 己 在 想 什 麼 與 做 什 麼! 否 則, 面 試 官 無 法 知 道 你 如 何 處 理 複 雜 的 程 式 設 計 問 題 解 決 問 題 接 下 來 是 時 候 來 好 好 解 決 問 題 了, 但 不 要 只 是 一 頭 栽 進 去! 首 先, 你 要 充 分 地 了 解 題 目 的 意 思 你 應 試 著 找 出 一 個 例 子 來 幫 助 自 己 了 解 問 題, 接 著 集 中 精 神 在 你 將 用 來 解 決 問 題 的 演 算 法 上 之 後 向 面 試 官 解 釋 你 的 解 決 方 法 和 程 式 碼 下 面 的 步 驟 將 帶 你 完 成 走 過 此 流 程 :
第 三 章 程 式 問 題 的 應 對 方 法 23 基 本 步 驟 解 決 問 題 最 好 的 方 式 便 是 有 條 不 紊 的 處 理 它 以 下 是 建 議 採 取 的 步 驟 : 1. 請 確 保 你 了 解 問 題 你 最 初 對 於 問 題 的 設 想 可 能 是 錯 誤 的, 或 者 面 試 官 對 於 問 題 的 解 釋 可 能 很 簡 短 或 是 難 以 理 解 在 這 種 不 了 解 問 題 的 情 況 下, 你 無 法 正 確 地 解 決 問 題 來 證 明 自 己 的 技 能 不 要 羞 於 對 面 試 官 提 問, 而 且 在 真 正 地 了 解 問 題 前 不 要 開 始 著 手 處 理 它 面 試 官 極 有 可 能 是 故 意 說 些 模 糊 的 解 說, 以 確 定 你 是 否 會 試 著 去 了 解 真 正 的 問 題 2. 當 你 明 白 這 個 問 題 之 後, 嘗 試 找 出 範 例 這 個 例 子 可 能 引 領 出 解 決 問 題 的 方 法, 或 者 找 出 尚 未 釐 清 的 誤 解 從 例 子 開 始 著 手 還 可 以 表 現 出 有 條 不 紊 的 邏 輯 思 考 過 程 此 外, 在 無 法 馬 上 找 出 解 決 方 法 時, 範 例 更 是 特 別 有 用 在 你 解 決 問 題 前, 請 確 保 你 了 解 問 題 然 後 以 例 子 來 更 加 鞏 固 你 的 理 解 3. 專 注 在 你 將 用 來 解 決 問 題 的 演 算 法 上 可 以 預 料 的, 找 出 演 算 法 通 常 需 要 很 長 的 時 間 與 更 多 的 範 例 在 這 個 過 程 中, 與 面 試 官 的 互 動 便 變 得 相 當 重 要 如 果 你 靜 靜 地 站 在 白 板 前, 面 試 官 沒 有 辦 法 知 道 你 是 否 正 在 想 辦 法 解 決 問 題, 或 者 你 根 本 是 毫 無 線 索 與 你 的 面 試 官 聊 天! 並 告 訴 他 自 己 正 在 做 什 麼 例 如, 你 可 能 會 這 樣 說 : 我 在 想 是 否 要 將 這 些 值 存 放 在 陣 列 中 然 後 做 排 序, 但 是 我 不 認 為 這 是 個 好 方 法, 因 為 如 此 一 來 便 不 能 直 接 透 過 數 值 找 到 我 要 的 元 素 這 樣 更 顯 示 出 你 的 才 能, 而 且 可 能 會 令 面 試 官 給 予 一 些 暗 示 他 可 能 會 這 樣 說 : 你 非 常 接 近 解 答 了 你 真 的 需 要 透 過 數 值 來 搜 尋 元 素 嗎? 也 許 你 能 解 決 問 題 也 許 需 要 花 很 長 時 間, 也 因 此 在 有 完 整 的 解 法 前 你 可 能 會 情 不 自 禁 地 想 開 始 撰 寫 程 式 請 不 要 這 樣 做! 試 著 想 想 你 會 想 跟 哪 一 種 人 一 起 工 作 呢? 一 個 對 問 題 思 考 了 很 長 一 段 時 間, 然 後 正 確 無 誤 地 開 始 著 手 撰 寫 程 式 的 人 或 是 另 一 個 貿 然 進 入 問 題 之 中 寫 起 程 式, 撰 寫 時 遇 到 了 一 堆 錯 誤 與 問 題, 並 且 對 於 自 己 未 來 的 方 向 沒 有 頭 緒 的 人 這 答 案 應 該 是 相 當 明 顯 4. 當 你 找 到 演 算 法 以 及 實 作 它 的 方 法 後, 向 面 試 官 說 明 你 的 解 法 這 給 了 他 一 個 機 會 在 你 寫 程 式 前 評 價 你 的 解 法 你 的 面 試 官 可 能 會 說 : 這 方 法 聽 起 來 不 錯, 繼 續 把 它 的 程 式 碼 實 作 出 來 吧 或 者 是 說 : 這 並 不 完 全 正 確, 因 為 你 不 能 在 雜 湊 表 使 用 那 樣 的 方 式 搜 尋 無 論 何 種 情 況, 你 將 獲 得 寶 貴 的 資 訊 5. 當 你 在 撰 寫 程 式 時, 很 重 要 的 是 要 解 釋 自 己 在 做 什 麼 例 如, 你 可 能 會 說 : 在 這 段 程 式 碼 中, 我 會 將 陣 列 的 值 初 始 化 為 零 這 樣 的 描 述 能 讓 面 試 官 更 容 易 看 懂 你 的 程 式 碼
24 恭 喜 你 錄 取 了! 程 式 設 計 師 如 何 贏 在 面 試 在 你 針 對 自 己 的 解 決 方 法 撰 寫 程 式 之 前 與 之 中, 請 向 面 試 官 解 釋 它 保 持 彼 此 的 對 話! 6. 必 要 時 提 出 問 題 一 般 而 言, 提 出 平 常 你 會 查 看 參 考 資 料 的 問 題 並 不 會 受 到 責 難 然 而 很 顯 然 地, 你 不 能 提 出 以 下 的 問 題, 我 該 如 何 解 決 這 個 問 題 呢?, 但 下 面 這 樣 的 問 題 卻 是 可 被 接 受 的 : 我 不 記 得 該 用 什 麼 格 式 的 字 串 來 列 印 出 本 地 的 日 期, 可 以 告 訴 我 嗎? 雖 然 不 問 更 好, 但 詢 問 這 樣 的 問 題 是 無 妨 的 7. 當 你 寫 的 程 式 有 問 題 時, 立 即 找 一 個 例 子 來 驗 證 程 式 碼 的 正 確 性 這 個 步 驟 可 以 證 明 至 少 你 的 程 式 在 這 個 例 子 下 可 以 執 行 它 也 說 明 了 你 如 何 檢 查 程 式 與 尋 找 錯 誤 的 邏 輯 思 考 過 程 這 個 範 例 還 能 幫 你 找 出 解 法 中 的 小 錯 誤 8. 請 務 必 檢 查 你 的 程 式 沒 有 錯 誤, 並 且 在 所 有 特 殊 情 況 尤 其 是 邊 界 條 件 下 的 運 作 是 正 常 的 程 式 設 計 師 在 面 試 時 常 會 忽 略 許 多 錯 誤 和 特 殊 情 況, 卻 忘 記 這 暗 示 著 你 可 能 會 在 工 作 時 也 遺 忘 它 們 例 如, 如 果 動 態 配 置 記 憶 體, 請 檢 查 配 置 是 否 成 功 ( 如 果 時 間 因 素 不 允 許 你 進 行 全 面 的 檢 查, 至 少 告 訴 面 試 官 你 應 該 做 這 類 的 檢 查 ) 如 果 你 的 解 說 中 能 包 含 這 些 錯 誤 和 特 殊 情 況, 會 令 面 試 官 對 你 印 象 深 刻, 而 且 這 些 習 慣 能 夠 幫 助 你 正 確 地 解 決 問 題 嘗 試 找 出 一 個 例 子, 並 檢 查 所 有 的 錯 誤 和 特 殊 情 況 一 旦 你 試 過 一 個 範 例, 並 且 認 為 程 式 碼 正 確 無 誤, 面 試 官 也 許 會 針 對 你 的 程 式 提 出 一 些 問 題 大 致 上, 這 些 問 題 會 集 中 在 程 式 的 執 行 時 間 有 沒 有 其 他 取 代 的 實 作 方 式 和 程 式 的 複 雜 性 上 如 果 你 的 面 試 官 沒 有 問 這 些 問 題, 你 應 該 主 動 地 提 出, 以 顯 示 出 你 對 這 類 問 題 的 了 解 例 如, 你 可 以 說 : 這 個 作 法 具 有 線 性 的 執 行 時 間, 因 為 必 須 檢 查 所 有 輸 入 的 數 值, 所 以 這 樣 的 複 雜 度 已 經 是 最 好 的 了 動 態 記 憶 體 配 置 將 會 減 慢 速 度, 而 使 用 遞 迴 也 提 高 了 成 本 當 你 碰 到 瓶 頸 時 在 面 試 的 過 程 中, 被 卡 在 一 個 問 題 上 是 可 以 預 想 的 事, 而 且 也 是 面 試 中 相 當 重 要 的 部 分 面 試 官 會 想 藉 此 觀 察 你 無 法 馬 上 回 答 問 題 時 的 反 應 放 棄 回 答 或 感 到 挫 折 都 是 相 當 糟 糕 的 事 情 相 反 地, 你 應 當 表 現 出 對 問 題 的 強 烈 興 趣, 並 不 斷 地 嘗 試 找 出 解 答 回 到 最 初 的 範 例 嘗 試 著 執 行 並 分 析 你 在 做 什 麼 試 著 將 你 的 範 例 由 特 定 的 例 子 延 伸 為 通 用 的 例 子 你 也 許 需 要 使 用 非 常 詳 細 的 範 例 這 樣 做 是 無 妨 的, 因 為 它 向 面 試 官 顯 示 出 你 對 於 找 到 正 確 方 法 的 堅 持
第 三 章 程 式 問 題 的 應 對 方 法 25 當 所 有 步 驟 都 失 敗 了, 請 回 到 最 初 那 個 具 體 的 例 子 上 嘗 試 將 具 體 的 例 子 變 成 通 用 的 例 子, 並 從 那 裡 找 到 解 法 嘗 試 不 同 的 資 料 結 構 也 許 使 用 鏈 結 串 列 陣 列 雜 湊 表 或 二 元 搜 尋 樹 會 有 所 幫 助 如 果 題 目 中 使 用 的 是 一 種 不 常 用 的 資 料 結 構, 請 找 出 它 與 你 熟 悉 的 資 料 結 構 之 間 的 相 似 之 處 使 用 正 確 的 資 料 結 構, 往 往 會 簡 化 問 題 考 慮 使 用 程 式 語 言 中 較 少 使 用 或 更 進 階 的 功 能 有 時 解 決 問 題 的 關 鍵 可 能 在 這 些 功 能 之 中 有 時, 不 同 的 資 料 結 構 或 程 式 語 言 的 進 階 功 能 是 解 決 問 題 的 關 鍵 即 使 在 你 並 沒 有 被 題 目 卡 住 時, 仍 然 會 遇 到 一 些 問 題 你 可 能 會 遺 忘 使 用 簡 潔 而 有 力 的 實 作 方 式, 而 不 小 心 寫 了 太 多 的 程 式 碼 幾 乎 所 有 接 受 面 試 時 的 問 題 都 有 簡 短 的 答 案 你 很 少 需 要 撰 寫 超 過 15 行 的 程 式 碼, 超 過 30 行 更 是 幾 乎 沒 有 如 果 你 寫 了 一 堆 程 式 碼, 就 表 示 著 你 可 能 正 朝 著 錯 誤 的 方 向 前 進 分 析 你 的 答 案 一 旦 你 對 於 問 題 提 出 了 解 法, 接 著 你 可 能 會 被 問 到 有 關 於 它 的 執 行 效 率 一 般 而 言, 你 必 須 在 你 的 方 法 與 另 一 個 可 能 的 解 決 方 法 之 間 做 出 分 析, 指 出 在 哪 些 情 況 下 哪 個 方 法 是 較 為 有 利 的 通 常 比 較 著 重 於 記 憶 體 或 空 間 的 使 用 情 況 上, 特 別 是 當 這 些 方 法 涉 及 遞 迴 時 為 了 讓 面 試 官 留 下 良 好 印 象, 對 於 Big-O 的 分 析 是 相 當 重 要 的 Big-O 分 析 是 種 衡 量 演 算 法 效 率 的 方 法, 它 是 以 輸 入 個 數 的 大 小 來 計 算 該 演 算 法 所 需 時 間 的 函 數, 是 一 個 簡 單 用 以 分 類 演 算 法 相 對 效 率 的 方 法, 而 並 非 正 式 的 基 準 值 本 書 中 多 數 程 式 問 題 的 解 答 都 會 包 含 執 行 時 間 的 分 析, 以 幫 助 你 了 解 該 演 算 法 分 析 兩 個 範 例 讓 我 們 從 範 例 來 了 解 Big-O 分 析 第 一 個 範 例 是 設 計 一 個 回 傳 非 負 數 陣 列 中 最 大 值 的 簡 單 函 式 該 陣 列 的 大 小 為 n 要 實 作 這 個 函 式, 至 少 有 兩 種 簡 單 的 方 法 在 第 一 個 方 法 中, 首 先 要 先 記 錄 陣 列 中 的 第 一 個 成 員 的 值 為 何, 接 著 會 對 陣 列 的 其 他 成 員 做 比 較, 每 次 比 較 時 會 將 記 錄 的 值 改 為 較 大 的 值, 等 到 所 有 成 員 都 比 較 完 後, 所 記 錄 的 值 即 是 陣 列 中 的 最 大 值 這 種 實 作 方 式 被 稱 為 CompareToMax, 它 的 程 式 如 下 :
26 恭 喜 你 錄 取 了! 程 式 設 計 師 如 何 贏 在 面 試 /* Returns the largest integer in the array */ int CompareToMax(int array[], int n) { int curmax, i; /* Make sure that there is at least one element in the array. */ if (n <= 0) return -1; /* Set the largest number so far to the first array value. */ curmax = array[0]; /* Compare every number with the largest number so far. */ for (i = 1; i < n; i++) { if (array[i] > curmax) { curmax = array[i]; return curmax; 第 二 個 方 法 則 是 將 陣 列 中 每 個 成 員 都 與 其 他 所 有 成 員 作 比 較, 如 果 所 有 其 他 的 值 都 小 於 或 等 於 該 成 員, 則 該 成 員 的 值 必 為 最 大 值 這 種 方 法 稱 為 CompareToAll, 程 式 碼 如 下 : /* Returns the largest integer in the array */ int CompareToAll(int array[], int n) { int i, j; bool ismax; /* Make sure that there is at least one element in the array. */ if (n <= 0) return -1; */ for (i = n-1; i > 0; i--) { ismax = true; for (j = 0; j < n; j++) { /* See if any value is greater. */ if (array[j] > array[i]) ismax = false; /* array[i] is not the largest value.
第 三 章 程 式 問 題 的 應 對 方 法 27 */ /* If ismax is true, no larger value exists; array[i] is max. if (ismax) break; return array[i]; 這 兩 個 方 法 都 能 正 確 地 回 傳 最 大 值 問 題 是, 哪 個 效 率 較 高 呢? 也 許 可 以 試 著 對 兩 個 方 法 做 基 準 測 試 (benchmark), 但 對 於 所 有 的 可 能 解 法 做 這 樣 的 測 試 是 不 實 際 而 且 沒 有 效 率 我 們 需 要 有 方 法 能 夠 不 做 任 何 測 試 就 預 測 出 演 算 法 的 效 能 而 Big-O 分 析 便 使 你 能 夠 做 到 這 點 : 比 較 不 同 演 算 法 的 相 對 效 能 Big-O 分 析 如 何 運 作 在 Big-O 分 析 中, 輸 入 數 量 的 大 小 被 假 設 為 n 在 上 述 例 子 中,n 表 示 陣 列 中 成 員 的 數 量 在 其 他 的 問 題 中,n 則 可 能 代 表 鏈 結 串 列 的 節 點 數, 或 資 料 型 態 的 位 元 數, 或 雜 湊 表 中 成 員 的 數 量 等 等 在 了 解 n 的 意 思 後, 你 必 須 判 斷 這 n 個 輸 入 項 目 執 行 了 多 少 次 動 作 動 作 是 個 模 糊 的 字 眼, 因 為 不 同 類 型 的 演 算 法 彼 此 間 有 著 很 大 的 不 同 通 常, 動 作 可 能 是 將 輸 入 值 加 上 一 個 常 數 建 立 新 的 輸 入 項 目 或 刪 除 輸 入 值 Big-O 分 析 將 這 些 動 作 被 認 定 為 等 價 在 CompareToMax 和 CompareToAll 中, 動 作 則 是 指 對 陣 列 中 的 元 素 與 另 一 個 元 素 的 值 做 比 較 在 CompareToMax 中, 每 個 陣 列 元 素 都 會 被 比 較 過 一 次 因 此,n 個 輸 入 項 目 總 共 被 需 要 n 次 動 作 ( 每 個 項 目 各 一 次 ) 因 此 是 O(n), 通 常 稱 為 線 性 時 間 (linear time), 即 執 行 這 個 演 算 法 所 需 時 間 會 隨 著 輸 入 項 目 的 增 加 而 線 性 增 加 你 可 能 會 注 意 到, 除 了 檢 查 每 個 元 素 之 外, 還 需 要 確 保 陣 列 內 不 為 空 的 的 檢 查 步 驟, 以 及 初 始 化 curmax 變 數 的 步 驟 因 此 考 慮 這 些 額 外 的 運 算,O(n + 2) 似 乎 更 加 準 確 然 而, 在 Big-O 分 析 中, 當 n 趨 於 無 窮 大 時,n 和 n + 2 是 幾 乎 相 等 的, 也 因 此 常 數 項 可 以 被 忽 略 同 樣 地, 對 於 一 個 執 行 時 間 為 n + n 2 的 演 算 法, 當 n 很 大 時,n 2 與 n + n 2 間 的 差 異 也 是 微 不 足 道 因 此,Big-O 分 析 只 會 保 留 最 高 次 方 的 項 目, 其 他 都 會 被 省 略 以 上 述 的 例 子 來 說 n 就 是 最 高 次 方 因 此,CompareToMax 為 O(n) 相 較 於 CompareToMax,CompareToAll 的 分 析 則 較 為 困 難 首 先, 我 們 必 須 假 設 最 大 值 會 落 在 陣 列 中 的 何 處 我 們 先 假 設 最 大 值 位 在 陣 列 的 最 後 在 這 種 情 況 下, 這 個 函 式 就 會 對 每 個 項 目 都 與 其 它 項 目 都 做 一 次 比 較 所 以 共 有 n*n 次 比 較, 可 推 得 這 是 一 個 O(n 2 ) 的 演 算 法
28 恭 喜 你 錄 取 了! 程 式 設 計 師 如 何 贏 在 面 試 到 目 前 為 止 的 分 析 表 示,CompareToMax 為 O(n) 而 CompareToAll 是 O(n 2 ) 這 表 示 當 陣 列 的 大 小 增 加 時, 在 CompareToAll 所 做 的 比 較 次 數 將 遠 大 於 CompareToMax 以 30,000 個 陣 列 元 素 為 例,CompareToMax 會 比 較 30,000 次, 而 CompareToAll 則 必 須 比 較 900,000,000 次 可 以 預 期 CompareToMax 會 比 較 快, 因 為 它 檢 查 的 次 數 較 CompareToAll 少 了 30,000 倍 事 實 上, 一 個 基 準 測 試 顯 示 CompareToMax 所 需 要 的 時 間 不 到 0.01 秒, 而 CompareToAll 則 需 要 23.99 秒 在 Big-O 分 析 之 中, 最 快 的 執 行 時 間 為 O(1) 而 這 樣 的 時 間 通 常 被 稱 為 常 數 的 執 行 時 間 有 著 常 數 執 行 時 間 的 演 算 法, 不 論 輸 入 數 量 的 大 小, 其 所 需 花 費 的 時 間 永 遠 是 固 定 的 最 佳 平 均 最 壞 情 況 你 可 能 會 認 為 這 種 比 較 不 利 於 CompareToAll, 因 為 我 們 假 設 最 大 值 是 在 陣 列 的 最 後 這 也 帶 出 一 個 重 要 議 題 : 最 佳 情 況 平 均 情 況 與 最 壞 的 情 況 在 分 析 CompareToAll 時 我 們 採 用 的 是 最 壞 情 況, 即 最 大 值 是 在 陣 列 的 最 末 端 然 而, 以 平 均 情 況 來 說, 最 大 值 應 該 在 陣 列 中 間 因 為 最 大 值 在 中 間, 你 只 需 檢 查 n / 2 次 因 此, 我 們 可 推 得 所 需 檢 查 的 次 數 為 n(n / 2) = n 2 / 2 這 似 乎 是 一 個 O(n 2 / 2) 的 執 行 時 間 接 著 我 們 必 須 思 考 1/2 倍 的 意 義 檢 查 每 個 值 的 實 際 所 需 時 間 高 度 依 賴 於 程 式 碼 轉 換 成 的 電 腦 指 令 與 CPU 執 行 那 些 指 令 的 速 度 因 此,1/2 並 不 具 有 太 大 意 義 甚 至 可 以 設 計 出 O(n 2 ) 的 演 算 法, 而 它 的 執 行 時 間 卻 比 O(n 2 / 2) 的 演 算 法 更 快 在 Big-O 分 析 中, 我 們 會 將 常 數 捨 棄, 因 此 平 均 情 況 下 的 CompareToAll 並 沒 有 比 最 壞 情 況 的 更 快 它 仍 然 為 O(n 2 ) 而 CompareToAll 中, 最 好 的 執 行 時 間 則 優 於 O(n 2 ) 在 最 佳 情 況 下, 最 大 值 是 在 陣 列 的 一 開 始 其 他 值 與 最 高 值 相 比 的 次 數 均 只 有 一 次, 也 因 此 結 果 是 O(n) 的 執 行 時 間 請 注 意, 在 CompareToMax 裡, 最 佳 情 況 平 均 情 況 最 差 情 況 的 執 行 時 間 是 相 同 的 不 管 陣 列 的 大 小, 該 演 算 法 的 複 雜 度 都 是 O(n) 可 以 主 動 去 詢 問 面 試 官, 這 問 題 中 他 們 最 感 興 趣 的 實 際 情 況 是 什 麼, 有 時 你 會 挖 掘 出 問 題 本 身 的 線 索 例 如, 有 些 排 序 演 算 法 在 輸 入 資 料 是 未 排 序 時 的 執 行 時 間 極 差, 但 卻 可 能 極 適 於 已 排 序 好 的 資 料 如 何 進 行 Big-O 分 析 一 般 而 言,Big-O 執 行 時 間 分 析 的 步 驟 如 下 :
第 三 章 程 式 問 題 的 應 對 方 法 29 1. 弄 清 楚 輸 入 是 什 麼 以 及 n 代 表 的 意 義 2. 將 演 算 法 執 行 的 運 算 次 數 以 n 來 表 示 3. 只 保 留 最 大 次 方 的 項 目, 省 略 其 他 項 目 4. 刪 除 所 有 常 數 項 只 要 能 夠 正 確 地 找 出 與 輸 入 大 小 有 關 的 運 算, 對 於 你 想 測 試 的 演 算 法 進 行 Big-O 分 析 應 該 是 相 當 簡 單 的 最 佳 化 與 Big-O 分 析 演 算 法 的 最 佳 化 不 一 定 能 夠 對 整 體 執 行 時 間 產 生 預 期 的 變 化 以 CompareToAll 的 最 佳 化 為 例, 我 們 試 著 不 對 每 個 項 目 進 行 比 較, 而 只 對 在 該 項 目 後 的 所 有 項 目 做 比 較 因 為 在 該 項 目 之 前 的 每 個 成 員 早 就 已 經 與 該 項 目 做 過 一 次 比 較, 因 此 如 果 只 比 較 該 項 目 之 後 的 所 有 項 目, 這 演 算 法 的 執 行 結 果 依 然 是 正 確 的 在 這 樣 的 最 佳 化 之 下, 它 的 最 壞 情 況 為 何 呢? 第 一 個 值 與 n 個 項 目 做 比 較, 第 二 個 則 與 為 n 1 個 項 目 做 比 較, 第 三 個 則 是 n 2, 最 後 可 得 n +(n 1)+(n 2) +(n 3)+... + 1 化 簡 後 可 推 得 n 2 / 2 + n / 2 n 2 是 最 高 次 項, 因 此 最 佳 化 後 的 演 算 法 在 最 壞 情 況 下 仍 然 需 要 O(n 2 ) 的 執 行 時 間 對 於 很 大 的 輸 入 值 而 言, 我 們 對 演 算 法 所 做 的 最 佳 化 並 沒 有 真 正 影 響 其 執 行 時 間 總 結 在 面 試 時 表 現 出 你 解 決 問 題 的 方 式 會 決 定 你 是 否 能 夠 得 到 這 份 工 作, 因 此 如 何 正 確 地 回 答 問 題 是 件 相 當 重 要 的 事 情 面 試 時 的 問 題 往 往 只 會 越 來 越 困 難, 所 以 你 可 能 會 需 要 面 試 官 偶 爾 給 你 提 示, 這 是 很 正 常 的 事 通 常 你 會 使 用 目 前 主 流 的 程 式 語 言 來 撰 寫 程 式, 但 程 式 語 言 的 選 擇 還 是 得 看 你 所 應 徵 的 工 作 內 容 決 定, 所 以 請 確 定 自 己 熟 悉 該 工 作 所 需 的 程 式 語 言 在 你 嘗 試 解 決 每 道 問 題 時, 盡 可 能 與 面 試 官 保 持 互 動 讓 他 知 道 你 在 分 析 問 題 時 或 者 寫 程 式 時 的 思 考 邏 輯 首 先 確 保 你 了 解 問 題, 然 後 試 著 以 一 些 例 子 確 認 自 己 的 理 解 接 著 選 擇 一 個 可 以 在 這 例 子 中 正 常 運 作 的 演 算 法 此 外, 不 要 忘 了 測 試 特 殊 情 況 如 果 你 被 問 題 卡 住, 請 試 試 更 多 的 範 例 或 選 用 不 同 的 演 算 法 來 解 決 問 題 在 尋 找 其 他 方 法 來 解 決 問 題 時, 別 忘 了 想 想 程 式 語 言 裡 面 比 較 少 用 或 者 更 進 階 的 功 能 如 果 面 試 官 請 你 分 析 演 算 法 的 效 率 時, 用 Big-O 時 間 複 雜 度 分 析 來 說 明 就 很 充 分 了 可 在 線 性 或 常 數 時 間 內 執 行 的 演 算 法 通 常 是 比 較 好 的