การวิเคราะห์ค่าตัดจำหน่าย สำหรับลำดับของการดำเนินการจะใช้เพื่อกำหนดเวลารัน เวลาเฉลี่ยที่ต้องการตามลำดับ In ไม่สามารถถือเป็นการวิเคราะห์กรณีเฉลี่ยบนอัลกอริทึมได้ เนื่องจากไม่ได้ใช้สถานการณ์จำลองกรณีเฉลี่ยเสมอไป มีบางกรณีที่เกิดขึ้นเป็นสถานการณ์สมมติกรณีที่เลวร้ายที่สุดของการวิเคราะห์ ดังนั้น การวิเคราะห์ที่ตัดจำหน่ายสามารถถือเป็นการวิเคราะห์กรณีที่เลวร้ายที่สุดสำหรับการดำเนินการหลายรายการในลำดับ ที่นี่ค่าใช้จ่ายในการดำเนินการแต่ละอย่างแตกต่างกันและสำหรับบางส่วนก็สูง ปัญหานี้เป็นมุมมองทั่วไปโดยใช้ตัวนับไบนารี
มาดูการทำงานและการใช้งานในภาษาโปรแกรม c++ กัน จะได้เข้าใจแนวคิดชัดเจน
ตัวนับไบนารี k-bit ถูกใช้งานโดยใช้อาร์เรย์ไบนารีที่มีความยาว 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/k 2 k ในจำนวนการพลิก
นี่คือ GP ที่มี HP เป็นตัวส่วน
ผลรวมของการพลิก
ผลรวม =n + n/2 + n/4 + ….. + n/k
2
ตอนนี้ ค่าใช้จ่ายในการดำเนินการที่มีกลิ่นหอมคือ O(n) / 2n =O(1)
ลำดับคือ O(1) ซึ่งไม่เป็นสัดส่วนกับ n จำนวนบิตในตัวเลข
