資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中計數器增量的攤還分析
攤還分析用於確定一系列操作的執行時間，即序列所需的平均時間。它不能被視為對演算法進行的平均情況分析，因為它並不總是採用平均情況。有些情況會作為分析的最壞情況出現。因此，攤還分析可以被視為對序列中多個操作的最壞情況分析。這裡，每個操作的成本是不同的，對於某些操作，成本很高。這個問題是使用二進位制計數器的一般檢視。
讓我們看看在 c++ 程式語言中的工作原理和實現，以便我們能夠清楚地理解這些概念。
k 位二進位制計數器使用長度為 k 的二進位制陣列實現，該陣列最初的值為 0。在此值上，增量操作執行多次。以下是 8 位二進位制陣列在對其執行增量操作時的行為方式。
最初，00000000 > 00000001 > 00000010 > 00000011 > 00000100 > 00000101 >.... > 11111111。
此邏輯用於檢查從數字的最後一位開始的第一個 0 的出現，並將其翻轉為 1，並將所有依次跟隨它的位翻轉為 0。
示例
#include <iostream>
using namespace std;
int main(){
int number[] = {1,0,0,1,0,1,1,1};
int length = 8;
int i = length - 1;
while (number[i] == 1) {
number[i] = 0;
i--;
}
if (i >= 0)
str[i] = 1;
for(int i = 0 ; i<length ; i++)
cout<<number[i]<<" ";
}輸出
1 0 0 1 0 0 0 0
在這個問題中，每個操作的成本是恆定的，並且不依賴於位的數量，
這裡序列成本的漸近分析為 O(n)。
在 n 次操作中執行的翻轉總數為 - n + n/2 + n/4 + ….. + n/k2 k 為翻轉次數。
這是一個分母為調和級數的等比級數。
翻轉總和
總和 = n + n/2 + n/4 + ….. + n/k2 < n/(1-1/2) = 2n
現在，操作的攤還成本為 O(n) / 2n = O(1)
階為 O(1)，它與數字中位的數量 n 不成比例。
更新於: 2019-10-24
477 次檢視
廣告