第 五 章:優化算法_《C++性能優化指南》_notes

優化算法

      • 第五章重難點詳解與代碼實戰
      • 編譯與測試說明
      • 第五章核心知識點整理
        • 重難點梳理
      • 第一部分：多選題（10道）
      • 第二部分：設計題（5道）
      • 答案與詳解
        • 多選題答案：
      • 設計題參考實現（以題目2為例）
        • 代碼說明：
      • 測試用例設計要點

第五章重難點詳解與代碼實戰

  1. 時間復雜度分析（5.1節）
    重點：掌握大O符號含義，區分最優/平均/最差情況時間復雜度。
    示例：插入排序時間復雜度分析
#include <iostream>
#include <vector>
using namespace std;// 插入排序實現
void insertionSort(vector<int>& arr) {for (int i = 1; i < arr.size(); ++i) {int key = arr[i];int j = i-1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}int main() {vector<int> test1 = {5, 2, 4, 6, 1, 3}; // 平均情況insertionSort(test1);cout << "Sorted average case: ";for (int num : test1) cout << num << " ";cout << endl;vector<int> test2 = {6, 5, 4, 3, 2, 1}; // 最壞情況（逆序）insertionSort(test2);cout << "Sorted worst case: ";for (int num : test2) cout << num << " ";return 0;
}

測試：觀察不同輸入下的執行時間差異（平均O(n2)，最優O(n)）。

  1. 查找算法優化（5.3節）
    重點：線性查找 vs 二分查找時間復雜度差異。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 線性查找 O(n)
int linearSearch(const vector<int>& arr, int target) {for (int i = 0; i < arr.size(); ++i) {if (arr[i] == target) return i;}return -1;
}// 二分查找 O(log n)
int binarySearch(const vector<int>& arr, int target) {int left = 0, right = arr.size()-1;while (left <= right) {int mid = left + (right - left)/2;if (arr[mid] == target) return mid;if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}int main() {vector<int> arr = {1, 3, 5, 7, 9, 11};int target = 7;cout << "Linear search index: " << linearSearch(arr, target) << endl;cout << "Binary search index: " << binarySearch(arr, target) << endl;// 性能對比測試（需添加計時邏輯）return 0;
}

優化點：預處理排序后使用二分查找大幅提升效率。

  1. 排序算法優化（5.4節）
    重點：快速排序優化（三數取中法避免最壞情況）
#include <iostream>
#include <vector>
using namespace std;// 三數取中法選擇pivot
int medianOfThree(vector<int>& arr, int left, int right) {int mid = left + (right - left)/2;if (arr[mid] < arr[left]) swap(arr[left], arr[mid]);if (arr[right] < arr[left]) swap(arr[left], arr[right]);if (arr[mid] < arr[right]) swap(arr[mid], arr[right]);return right;
}// 快速排序優化實現
void quickSort(vector<int>& arr, int left, int right) {if (left >= right) return;// 選擇pivot并分區int pivot = medianOfThree(arr, left, right);int i = left - 1;for (int j = left; j < right; ++j) {if (arr[j] <= arr[pivot]) {i++;swap(arr[i], arr[j]);}}swap(arr[i+1], arr[pivot]);int partitionIndex = i + 1;quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right);
}int main() {vector<int> test = {3, 6, 8, 10, 1, 2, 1};quickSort(test, 0, test.size()-1);cout << "Optimized QuickSort: ";for (int num : test) cout << num << " ";return 0;
}

測試：對比標準快速排序與優化版本在逆序數組中的性能。

  1. 優化模式：緩存（5.5.4節）
    示例：斐波那契數列的緩存優化
#include <iostream>
#include <unordered_map>
using namespace std;unordered_map<int, int> cache;// 帶緩存的遞歸斐波那契
int fib(int n) {if (n <= 1) return n;if (cache.find(n) != cache.end()) return cache[n];cache[n] = fib(n-1) + fib(n-2);return cache[n];
}int main() {cout << "Fib(10): " << fib(10) << endl;  // 55cout << "Fib(20): " << fib(20) << endl;  // 6765return 0;
}

優化效果：時間復雜度從O(2?)降為O(n)。

  1. 斯特潘諾夫抽象懲罰（5.6節）
    重點：泛型編程帶來的性能損耗分析
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 自定義簡單排序（無抽象）
void simpleSort(int* arr, int size) {for (int i=0; i<size; ++i)for (int j=i+1; j<size; ++j)if (arr[j] < arr[i])swap(arr[i], arr[j]);
}// 測試對比
int main() {vector<int> data(10000);generate(data.begin(), data.end(), rand);// 測試STL排序（模板抽象）auto stlData = data;sort(stlData.begin(), stlData.end());// 測試簡單排序（直接實現）auto simpleData = data;simpleSort(&simpleData[0], simpleData.size());// 添加計時代碼比較性能差異return 0;
}

結論：抽象層級越高可能帶來額外開銷，需權衡可維護性與性能。

編譯與測試說明

  1. 所有代碼均使用C++11或更高標準編譯：
g++ -std=c++11 example.cpp -o example
  1. 添加計時邏輯推薦使用<chrono>庫：
#include <chrono>
auto start = chrono::high_resolution_clock::now();
// ...測試代碼...
auto end = chrono::high_resolution_clock::now();
cout << "Time: " << chrono::duration_cast<chrono::microseconds>(end-start).count() << "μs\n";

第五章核心知識點整理

重難點梳理
  1. 算法時間復雜度分析（最優/平均/最壞情況）
  2. 哈希表與二分查找的性能對比
  3. 排序算法的選擇策略（快速排序 vs 基數排序）
  4. 預計算與延遲計算的應用場景
  5. 緩存策略的失效處理機制
  6. 雙重檢查鎖定模式的應用
  7. 散列函數設計原則
  8. 分治策略在排序中的應用
  9. 算法選擇時的內存局部性考量
  10. 攤銷時間復雜度分析

第一部分：多選題（10道）

  1. 關于哈希表查找性能，正確的是：
    A) 平均時間復雜度O(1)
    B) 最壞時間復雜度O(n)
    C) 適合有序數據查詢
    D) 空間復雜度總是O(n)

  2. 快速排序的優化策略包括：
    A) 三數取中法選擇樞軸
    B) 小數組切換插入排序
    C) 遞歸實現優先于迭代
    D) 處理重復元素的3-way partition

  3. 適合處理海量數據的排序算法：
    A) 基數排序
    B) 歸并排序
    C) 冒泡排序
    D) Flashsort

  4. 關于二分查找正確的是：
    A) 要求數據有序
    B) 時間復雜度O(n)
    C) 適合鏈表結構
    D) 可處理動態數據集

  5. 預計算模式的適用場景：
    A) 運行時頻繁計算的固定值
    B) 需要實時更新的動態數據
    C) 編譯期已知的常量表達式
    D) 內存敏感的低配設備

  6. 緩存失效的常見處理方式：
    A) LRU置換策略
    B) 定時強制刷新
    C) 寫穿透策略
    D) 哈希碰撞鏈表法

  7. 關于時間復雜度分析：
    A) 插入排序最壞O(n2)
    B) 快速排序平均O(n logn)
    C) 基數排序O(nk) k為位數
    D) 冒泡排序最優O(n)

  8. 雙重檢查鎖定用于：
    A) 單例模式初始化
    B) 線程安全緩存訪問
    C) 原子計數器操作
    D) 無鎖數據結構設計

  9. 影響算法實際性能的因素：
    A) 緩存命中率
    B) 分支預測效率
    C) 循環展開次數
    D) 指令流水線深度

  10. 關于分治策略：
    A) 快速排序基于分治
    B) 歸并排序需要額外空間
    C) 適合并行計算
    D) 總將問題分為兩等份

第二部分：設計題（5道）

題目1：延遲計算緩存系統
設計支持過期時間的緩存系統，要求：

  • 使用unordered_map存儲數據
  • 支持惰性清理過期條目
  • 線程安全的雙重檢查鎖定
  • 提供get/put接口

題目2：預計算優化斐波那契
實現基于預計算的斐波那契數列：

  • 編譯期生成前50項
  • 運行時直接查表
  • 處理溢出異常
  • 支持動態擴展

題目3：快速排序優化
實現優化的快速排序：

  • 三數取中選擇樞軸
  • 小數組切換插入排序
  • 迭代替代遞歸
  • 處理重復元素

題目4：哈希表性能優化
設計高性能哈希表：

  • 開放尋址法解決沖突
  • 負載因子超過0.75時擴容
  • 使用素數表控制容量
  • 支持移動語義

題目5：二分查找邊界處理
實現泛型二分查找：

  • 處理重復元素的第一個/最后一個位置
  • 支持旋轉有序數組
  • 異常安全保證
  • 性能測試對比線性搜索

答案與詳解

多選題答案：
  1. AB（哈希表平均O(1)，最壞O(n)）
  2. ABD（三數取中、小數組優化、3-way分區）
  3. ABD（基數、歸并、Flashsort適合大數據）
  4. A（必須有序）
  5. AC（固定值和編譯期計算）
  6. ABC（LRU、刷新、寫穿透）
  7. ABC（插入最壞O(n2)，快排平均O(n logn)，基數O(nk)）
  8. AB（單例和緩存訪問）
  9. ABCD（全部影響實際性能）
  10. ABC（快排分治、歸并需空間、可并行）

設計題參考實現（以題目2為例）

#include <iostream>
#include <vector>
#include <stdexcept>template<typename T>
class FibonacciCache {std::vector<T> cache;static const size_t INIT_SIZE = 50;
public:FibonacciCache() {cache.reserve(INIT_SIZE);cache.push_back(0);cache.push_back(1);for(size_t i=2; i<INIT_SIZE; ++i){T next = cache[i-1] + cache[i-2];if(next < cache[i-1]) throw std::overflow_error("Overflow in precomputation");cache.push_back(next);}}T get(size_t n) {while(n >= cache.size()){size_t i = cache.size();T next = cache[i-1] + cache[i-2];if(next < cache[i-1]) throw std::overflow_error("Overflow during expansion");cache.push_back(next);}return cache[n];}
};int main() {try {FibonacciCache<unsigned long long> fib;// Test precomputed valuesstd::cout << fib.get(10) << std::endl;  // 55std::cout << fib.get(49) << std::endl; // 7778742049// Test dynamic expansionstd::cout << fib.get(50) << std::endl; // 12586269025// Test overflow detectionFibonacciCache<unsigned> small_fib;small_fib.get(47); // Throw overflow} catch(const std::exception& e) {std::cerr << "Error: " << e.what() << std::endl;}return 0;
}
代碼說明：
  1. 模板類支持不同數值類型
  2. 編譯期預計算前50項
  3. 運行時動態擴展緩存
  4. 溢出檢測機制
  5. 異常安全保證

測試用例設計要點

  1. 驗證預計算正確性（n=10,49）
  2. 測試動態擴展能力（n=50）
  3. 邊界條件測試（n=0,1）
  4. 溢出異常檢測（unsigned類型n=47）
  5. 性能對比非預計算版本

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/75742.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/75742.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/75742.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

多版本PHP開發環境配置教程：WAMPServer下MySQL/Apache/MariaDB版本安裝與切換

多版本PHP開發環境配置教程：WAMPServer下MySQL/Apache/MariaDB版本安裝與切換

提示&#xff1a;文章寫完后&#xff0c;目錄可以自動生成&#xff0c;如何生成可參考右邊的幫助文檔 文章目錄 前言一、版本切換指南總結 前言 由于有幾個項目分別使用到PHP7.0 和7.4以及8.0版本&#xff0c;設置mysql也會根據PHP版本使用不同的版本&#xff0c;于是開始研究…
閱讀更多...
2024年數維杯數學建模C題天然氣水合物資源量評價解題全過程論文及程序

2024年數維杯數學建模C題天然氣水合物資源量評價解題全過程論文及程序

2024年數維杯數學建模 C題 天然氣水合物資源量評價 原題再現&#xff1a; 天然氣水合物&#xff08;Natural Gas Hydrate/Gas Hydrate&#xff09;即可燃冰&#xff0c;是天然氣與水在高壓低溫條件下形成的類冰狀結晶物質&#xff0c;因其外觀像冰&#xff0c;遇火即燃&#…
閱讀更多...
階段一：Java基礎語法

階段一：Java基礎語法

目標&#xff1a;掌握Java的基本語法&#xff0c;理解變量、數據類型、運算符、控制結構等。 1. Java開發環境搭建 安裝JDK配置環境變量編寫第一個Java程序 代碼示例&#xff1a; // HelloWorld.java public class HelloWorld { // 定義類名為 HelloWorldpublic static vo…
閱讀更多...
從0到1，解鎖Ant Design X的無限可能

從0到1，解鎖Ant Design X的無限可能

Ant Design X 是什么&#xff1f; 在人工智能飛速發展的當下&#xff0c;AI 驅動的界面已成為軟件開發的重要趨勢。而 Ant Design X 正是順應這一趨勢&#xff0c;于 2024 年應運而生的一款遵循 Ant Design 設計體系的 React UI 庫&#xff0c;它旨在幫助開發者輕松打造 AI 驅…
閱讀更多...
Graphpad Prism for Mac醫學繪圖

Graphpad Prism for Mac醫學繪圖

Graphpad Prism for Mac醫學繪圖 文章目錄 Graphpad Prism for Mac醫學繪圖一、介紹二、效果三、下載 一、介紹 GraphPad Prism for Mac是一款功能強大、易于使用的科學和統計分析軟件&#xff0c;適用于各種類型的數據處理和可視化需求。無論您是進行基礎研究、臨床試驗還是學…
閱讀更多...
mysqloracledb2 (uuid函數)

mysqloracledb2 (uuid函數)

項目場景&#xff1a; 創建一個32位的UUID 問題描述 原因分析&#xff1a; 解決方案&#xff1a; mysql內置UUID函數 SELECT UUID(); SELECT UUID_SHORT();oracle內置UUID函數 SELECT sys_guid() FROM dual;db2&#xff0c;模擬UUID函數 SELECT TEST || substr (CONCAT…
閱讀更多...
Android實踐開發制作小猴子摘桃小游戲

Android實踐開發制作小猴子摘桃小游戲

Android實踐制作小猴子摘桃小游戲 實踐素材項目源文件獲取&#xff1a;Android可能存在版本差異項目如果不能正確運行&#xff0c;可以使用里面的素材自己構建項目Android實踐制作小猴子摘桃小游戲Android實踐制作小猴子摘桃小游戲https://mp.weixin.qq.com/s/jNU_hVfj9xklsil…
閱讀更多...
Postman 下載文件指南：如何請求 Excel/PDF 文件？

Postman 下載文件指南：如何請求 Excel/PDF 文件？

在 Postman 中進行 Excel/PDF 文件的請求下載和導出&#xff0c;以下是簡明的步驟&#xff0c;幫助你輕松完成任務。首先&#xff0c;我們將從新建接口開始&#xff0c;逐步引導你完成整個過程。 Postman 請求下載/導出 excel/pdf 文件教程
閱讀更多...
重要重要！！fisher矩陣是怎么計算和更新的，以及計算過程中參數的物理含義

重要重要！！fisher矩陣是怎么計算和更新的，以及計算過程中參數的物理含義

fisher矩陣是怎么計算和更新的，以及計算過程中參數的物理含義 Fisher信息矩陣（Fisher Information Matrix, FIM）用于衡量模型參數估計的不確定性，其計算和更新在統計學、機器學習和優化中具有重要作用。以下是其計算和更新的關鍵步驟： 一、Fisher矩陣的計算 定義 Fisher…
閱讀更多...
21.Excel自動化：如何使用 xlwings 進行編程

21.Excel自動化：如何使用 xlwings 進行編程

一 將Excel用作數據查看器 使用 xlwings 中的 view 函數。 1.導包 import datetime as dt import xlwings as xw import pandas as pd import numpy as np 2.view 函數 創建一個基于偽隨機數的DataFrame&#xff0c;它有足夠多的行&#xff0c;使得只有首尾幾行會被顯示。 df …
閱讀更多...
Elasticsearch客戶端工具初探--kibana

Elasticsearch客戶端工具初探--kibana

1 Kibana簡介 Kibana是Elastic Stack&#xff08;ELK&#xff09;中的可視化工具&#xff0c;用于對Elasticsearch中存儲的數據進行搜索、分析和可視化展示。它提供了直觀的Web界面&#xff0c;支持日志分析、業務監控、數據探索等功能&#xff0c;廣泛應用于運維監控、安全分析…
閱讀更多...
珍珠港海軍造船廠的“水魔法”：PcVue賦能造船心臟

珍珠港海軍造船廠的“水魔法”：PcVue賦能造船心臟

導讀 項目背景 干船塢運作與控制需求 PcVue SCADA 系統的引入以及系統升級 項目成果 憑借更高的安全性&#xff0c;PcVue 對干船塢的充水和排水過程進行精準控制。 項目背景 珍珠港海軍基地與希卡姆空軍基地均依托這座歷史悠久的港口而發展&#xff0c;該港口在夏威夷原住…
閱讀更多...
3. 軸指令（omron 機器自動化控制器）——＞MC_GearInPos

3. 軸指令（omron 機器自動化控制器）——＞MC_GearInPos

機器自動化控制器——第三章 軸指令 17 MC_GearInPos變量?輸入變量?輸出變量?輸入輸出變量 功能說明?時序圖?重啟運動指令?多重啟動運動指令?異常 示例程序?動作示例?梯形圖?結構文本(ST) MC_GearInPos 設定主軸和從軸間的齒輪比&#xff0c;進行電子齒輪動作。 指定…
閱讀更多...
vue 加載動態效果，自行封裝組件

vue 加載動態效果，自行封裝組件

背景&#xff1a; 在項目開發中&#xff0c;會請求接口&#xff0c;就會遇到加載中、加載成功、加載失敗、和加載成功但暫無數據等情況。就自行封裝了一個加載組件。采用vue3elementsetup組合式寫法。 實現效果&#xff1a; 封裝組件&#xff1a; //封裝組件 <template>…
閱讀更多...
八目導航 version：1.2

八目導航 version：1.2

八目導航 version&#xff1a;1.2 網址&#xff1a;https://crbssseooebc.sealoshzh.site/ 日志&#xff1a; 1.美化了頁面 2.新增并替換了部分網址 3.不會出現危險網址提示(指的是進入八目導航時) 4.為網址圖標增加了動效 5.采用Vue3框架重新實現了該導航 注意&#xff1a;該…
閱讀更多...
WebWorkers在項目中的使用案例

WebWorkers在項目中的使用案例

Worker | 文檔 worker 線程的關閉在主線程和 worker 線程都能進行操作&#xff0c;但對 worker 線程的影響略有不同。 // main.js&#xff08;主線程&#xff09; const myWorker new Worker(/worker.js); // 創建worker myWorker.terminate(); // 關閉worker 復制代碼 // wor…
閱讀更多...
掌握Linux項目自動化構建：從零入門make與Makefile

掌握Linux項目自動化構建：從零入門make與Makefile

文章目錄 前言&#xff1a; 一、初識自動化構建工具1.1 什么是make/Makefile&#xff1f;1.2 快速體驗 二、深入理解核心機制2.1 依賴關系與依賴方法2.2 偽目標的妙用2.3 具體語法a.makefile的基本雛形b.makefile推導原則&#xff01; 三、更加具有通用型的makefile1. 變量定義…
閱讀更多...
深度分頁優化思路

深度分頁優化思路

深度分頁優化思路 思考以下問題 查詢以下SQL的流程是怎么樣的呢&#xff1f; 為什么只查詢10條數據需要7秒&#xff1f; # 查詢時間7秒 SELECT * FROM user ORDER BY age LIMIT 1000000, 10問題分析 為什么分頁查詢隨著翻頁的深入&#xff0c;會變得越來越慢。 其實&#xff0…
閱讀更多...
使用 Vite 提升前端開發體驗：入門與配置指南

使用 Vite 提升前端開發體驗：入門與配置指南

在現代前端開發中&#xff0c;構建工具的選擇對開發效率和項目性能有著至關重要的影響。Vite 是一個新興的前端構建工具&#xff0c;由 Vue.js 的作者尤雨溪開發&#xff0c;旨在通過利用現代瀏覽器的原生 ES 模塊特性&#xff0c;提供更快的開發服務器啟動速度和更高效的熱更新…
閱讀更多...
MYSQL基本語法使用

MYSQL基本語法使用

目錄 一、mysql之DML 增加語句 刪除語句和truncate 更新語句 replace語句 select查詢語句 二、select多種用法 查詢時的別名使用 分組 分組后的篩選 結果排序 分頁功能 分表 多表關聯查詢 練習題 一、單表查詢 二、多表查詢 前面已經學習了mysql的安裝和基本語…
閱讀更多...
最新文章

Copyright @ 2022~2023