Potential method
ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸಂಭಾವ್ಯ ವಿಧಾನವು ದತ್ತಾಂಶ ರಚನೆಯ ಪರಿಶೋಧಿತ ಸಮಯ ಮತ್ತು ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಬಳಸುವ ಒಂದು ವಿಧಾನವಾಗಿದೆ, ಇದು ವಿರಳವಾದ ಆದರೆ ದುಬಾರಿ ಕಾರ್ಯಾಚರಣೆಗಳ ವೆಚ್ಚವನ್ನು ಸುಗಮಗೊಳಿಸುವ ಕಾರ್ಯಾಚರಣೆಗಳ ಅನುಕ್ರಮಗಳ ಮೇಲೆ ಅದರ ಕಾರ್ಯಕ್ಷಮತೆಯ ಅಳತೆಯಾಗಿದೆ. ಸಾಲ ಮರುಪಾವತಿ ಸಮಯದ ವ್ಯಾಖ್ಯಾನ ಸಂಭಾವ್ಯ ವಿಧಾನದಲ್ಲಿ, ದತ್ತಾಂಶ ರಚನೆಯ ಸ್ಥಿತಿಗಳನ್ನು ಋಣಾತ್ಮಕವಲ್ಲದ ಸಂಖ್ಯೆಗಳಿಗೆ ನಕ್ಷೆ ಮಾಡುವ ಕಾರ್ಯವನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ಎಸ್ ದತ್ತಾಂಶ ರಚನೆಯ ಸ್ಥಿತಿಯಾಗಿದ್ದರೆ, ± (ಎಸ್) ಸಾಲ ಮರುಪಾವತಿ ವಿಶ್ಲೇಷಣೆಯಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಿದ ("ಪಾವತಿಸಿದ") ಕೆಲಸವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಆದರೆ ಇನ್ನೂ ನಿರ್ವಹಿಸಲಾಗಿಲ್ಲ. ಹೀಗಾಗಿ, ಆ ಸ್ಥಿತಿಯಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಸಂಭಾವ್ಯ ಶಕ್ತಿಯ ಪ್ರಮಾಣವನ್ನು ಲೆಕ್ಕ ಹಾಕುವಂತೆ φ (S) ಅನ್ನು ಪರಿಗಣಿಸಬಹುದು. ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಪ್ರಾರಂಭಿಸುವ ಕಾರ್ಯಾಚರಣೆಯ ಮೊದಲು ಸಂಭಾವ್ಯ ಮೌಲ್ಯವನ್ನು ಶೂನ್ಯ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಪರ್ಯಾಯವಾಗಿ, ಎಸ್ ಸ್ಥಿತಿಯಲ್ಲಿನ ಅಸ್ವಸ್ಥತೆಯ ಪ್ರಮಾಣವನ್ನು ಅಥವಾ ಆದರ್ಶ ಸ್ಥಿತಿಯಿಂದ ಅದರ ದೂರವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಎಂದು ± (ಎಸ್) ಅನ್ನು ಭಾವಿಸಬಹುದು. ಕೆಲವು ದತ್ತಾಂಶ ರಚನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳ ಅನುಕ್ರಮದೊಳಗೆ ಯಾವುದೇ ಪ್ರತ್ಯೇಕ ಕಾರ್ಯಾಚರಣೆಯಾಗಿರಲಿ, ಕಾರ್ಯಾಚರಣೆಗೆ ಮುಂಚಿತವಾಗಿ ದತ್ತಾಂಶ ರಚನೆಯ ಸ್ಥಿತಿಯನ್ನು ಸೂಚಿಸುವ ಮೊದಲು ಎಸ್ಬಿಒ ಮತ್ತು ಕಾರ್ಯಾಚರಣೆಯ ನಂತರ ಅದರ ಸ್ಥಿತಿಯನ್ನು ಸೂಚಿಸುವ ಸಾಫ್ಟರ್ ಒ ಪೂರ್ಣಗೊಂಡಿದೆ. ಒ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿದ ನಂತರ, ವಿಶ್ಲೇಷಣೆಯ ಉದ್ದಕ್ಕೂ ಸ್ಥಿರವಾಗಿ ಉಳಿಯಬೇಕಾದ ಅನುಪಾತದ ಋಣಾತ್ಮಕವಲ್ಲದ ಸ್ಥಿರಾಂಕ (ಸಮಯದ ಘಟಕಗಳಲ್ಲಿ) ಸಿ ಆಗಿದ್ದರೆ, ಒ ಕಾರ್ಯಾಚರಣೆಯ ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಅಂದರೆ, ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯವನ್ನು ಕಾರ್ಯಾಚರಣೆಯಿಂದ ತೆಗೆದುಕೊಳ್ಳುವ ನಿಜವಾದ ಸಮಯ ಮತ್ತು ಕಾರ್ಯಾಚರಣೆಯಿಂದ ಉಂಟಾಗುವ ಸಾಮರ್ಥ್ಯದಲ್ಲಿನ ವ್ಯತ್ಯಾಸದ ಸಿ ಪಟ್ಟು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ದೊಡ್ಡ O ಸಂಕೇತವನ್ನು ಬಳಸಿಕೊಂಡು ಅಸಿಂಪ್ಟೋಟಿಕ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯನ್ನು ಅಧ್ಯಯನ ಮಾಡುವಾಗ, ಸ್ಥಿರ ಅಂಶಗಳು ಅಪ್ರಸ್ತುತವಾಗಿರುತ್ತವೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸ್ಥಿರ C ಅನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಬಿಟ್ಟುಬಿಡಲಾಗುತ್ತದೆ. ಅದರ ಕೃತಕ ನೋಟದ ಹೊರತಾಗಿಯೂ, ಕಾರ್ಯಾಚರಣೆಗಳ ಸರಣಿಯ ಒಟ್ಟು ಮರುಪಾವತಿ ಸಮಯವು ಅದೇ ಸರಣಿಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ನಿಜವಾದ ಸಮಯದಲ್ಲಿ ಮಾನ್ಯವಾದ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಒದಗಿಸುತ್ತದೆ. ಕಾರ್ಯಾಚರಣೆಗಳ ಯಾವುದೇ ಅನುಕ್ರಮಕ್ಕೆ, ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಿಃ ಒಟ್ಟು ಸಾಲ ಮರುಪಾವತಿ ಸಮಯಃ ಒಟ್ಟು ನೈಜ ಸಮಯಃ ನಂತರಃ ಸಂಭಾವ್ಯ ಕಾರ್ಯ ಮೌಲ್ಯಗಳ ಅನುಕ್ರಮವು ದೂರದರ್ಶಕ ಸರಣಿಯನ್ನು ರೂಪಿಸುತ್ತದೆ, ಇದರಲ್ಲಿ ಆರಂಭಿಕ ಮತ್ತು ಅಂತಿಮ ಸಂಭಾವ್ಯ ಕಾರ್ಯ ಮೌಲ್ಯಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಪದಗಳು ಜೋಡಿಯಾಗಿ ರದ್ದುಗೊಳ್ಳುತ್ತವೆ. ಇದನ್ನು ಮರುಹೊಂದಿಸಿದಾಗ, ನಾವು ಪಡೆಯುತ್ತೇವೆಃ ಏಕೆಂದರೆ ಮತ್ತು, ಆದ್ದರಿಂದ ಒಂದು ಪ್ರತ್ಯೇಕ ಕಾರ್ಯಾಚರಣೆಯ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವು ಅದರ ನಿಜವಾದ ಸಮಯಕ್ಕಿಂತ ವ್ಯಾಪಕವಾಗಿ ಬದಲಾಗಬಹುದಾದರೂ, ಕಾರ್ಯಾಚರಣೆಗಳ ಸರಣಿಯ ನಿಜವಾದ ಸಮಯದಲ್ಲಿ ನಿಖರವಾದ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಒದಗಿಸಲು ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ಬಳಸಬಹುದು. ಕೆಟ್ಟ-ಕೇಸ್ ಇನ್ಪುಟ್ಗಳ ಅಮೋರ್ಟೈಸ್ಡ್ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಸಾಮಾನ್ಯವಾಗಿ, ಅಮೋರ್ಟೈಸ್ಡ್ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಇನ್ಪುಟ್ ಅನುಕ್ರಮದ ಬಗ್ಗೆ ಕೆಟ್ಟ ಕೇಸ್ ಊಹೆಯೊಂದಿಗೆ ಸಂಯೋಜಿಸಲಾಗುತ್ತದೆ. ಈ ಊಹೆಯೊಂದಿಗೆ, X ಎಂಬುದು ದತ್ತಾಂಶ ರಚನೆಯಿಂದ ನಿರ್ವಹಿಸಬಹುದಾದ ಒಂದು ರೀತಿಯ ಕಾರ್ಯಾಚರಣೆಯಾಗಿದ್ದರೆ, ಮತ್ತು n ಎಂಬುದು ನೀಡಲಾದ ದತ್ತಾಂಶ ರಚನೆಯ ಗಾತ್ರವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವ ಒಂದು ಪೂರ್ಣಾಂಕವಾಗಿದ್ದರೆ (ಉದಾಹರಣೆಗೆ, ಅದು ಒಳಗೊಂಡಿರುವ ವಸ್ತುಗಳ ಸಂಖ್ಯೆ), ನಂತರ X ಪ್ರಕಾರದ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು, n ಗಾತ್ರದ ದತ್ತಾಂಶ ರಚನೆಗಳ ಮೇಲಿನ ಕಾರ್ಯಾಚರಣೆಗಳ ಎಲ್ಲಾ ಸಂಭಾವ್ಯ ಅನುಕ್ರಮಗಳಲ್ಲಿ ಮತ್ತು ಅನುಕ್ರಮದೊಳಗಿನ X ಪ್ರಕಾರದ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳ ಒಐಗಳಲ್ಲಿ, ಕಾರ್ಯಾಚರಣೆಯ ಒಐಗಾಗಿ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯದ ಗರಿಷ್ಠ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಈ ವ್ಯಾಖ್ಯಾನದೊಂದಿಗೆ, ಕಾರ್ಯಾಚರಣೆಗಳ ಅನುಕ್ರಮವನ್ನು ನಿರ್ವಹಿಸುವ ಸಮಯವನ್ನು ಅನುಕ್ರಮದಲ್ಲಿ ಪ್ರತಿಯೊಂದು ರೀತಿಯ ಕಾರ್ಯಾಚರಣೆಗೆ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ಆ ರೀತಿಯ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯಿಂದ ಗುಣಿಸುವ ಮೂಲಕ ಅಂದಾಜು ಮಾಡಬಹುದು. ಉದಾಹರಣೆಗಳು ಡೈನಾಮಿಕ್ ರಚನೆಯು ವಸ್ತುಗಳ ಶ್ರೇಣಿಯನ್ನು ನಿರ್ವಹಿಸುವ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದ್ದು, ರಚನೆಯೊಳಗಿನ ಸ್ಥಾನಗಳಿಗೆ ಯಾದೃಚ್ಛಿಕ ಪ್ರವೇಶ ಮತ್ತು ರಚನೆಯ ಗಾತ್ರವನ್ನು ಒಂದರಿಂದ ಹೆಚ್ಚಿಸುವ ಸಾಮರ್ಥ್ಯ ಎರಡಕ್ಕೂ ಅವಕಾಶ ನೀಡುತ್ತದೆ. ಇದು ಜಾವಾದಲ್ಲಿ "ಅರೇಲಿಸ್ಟ್" ಪ್ರಕಾರವಾಗಿ ಮತ್ತು ಪೈಥಾನ್ನಲ್ಲಿ "ಲಿಸ್ಟ್" ಪ್ರಕಾರವಾಗಿ ಲಭ್ಯವಿದೆ. ಡೈನಾಮಿಕ್ ರಚನೆಯನ್ನು ದತ್ತಾಂಶ ರಚನೆಯಿಂದ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು, ಇದು ಕೆಲವು ಉದ್ದದ N ಅಂಶಗಳ ಶ್ರೇಣಿಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಜೊತೆಗೆ ಇದುವರೆಗೆ ಬಳಸಿದ ಶ್ರೇಣಿಯೊಳಗಿನ ಸ್ಥಾನಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ n ≤ N ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ರಚನೆಯೊಂದಿಗೆ, ಆಂತರಿಕ ರಚನೆಯ ಎ ಯ ಅದೇ ಕೋಶವನ್ನು ಪ್ರವೇಶಿಸುವ ಮೂಲಕ ಡೈನಾಮಿಕ್ ರಚನೆಗೆ ಯಾದೃಚ್ಛಿಕ ಪ್ರವೇಶಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು, ಮತ್ತು ಎನ್ <ಎನ್ ಕ್ರಿಯಾತ್ಮಕ ರಚನೆಯ ಗಾತ್ರವನ್ನು ಹೆಚ್ಚಿಸುವ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಕೇವಲ ಎನ್ ಅನ್ನು ಹೆಚ್ಚಿಸುವ ಮೂಲಕ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ಎನ್ = ಎನ್ ಆಗಿದ್ದಾಗ, ಎ ಗಾತ್ರವನ್ನು ಮರುಗಾತ್ರಗೊಳಿಸುವುದು ಅಗತ್ಯವಾಗಿರುತ್ತದೆ, ಮತ್ತು ಹಾಗೆ ಮಾಡಲು ಒಂದು ಸಾಮಾನ್ಯ ಕಾರ್ಯತಂತ್ರವೆಂದರೆ ಅದರ ಗಾತ್ರವನ್ನು ದ್ವಿಗುಣಗೊಳಿಸುವುದು, ಎ ಅನ್ನು 2n ಉದ್ದದ ಹೊಸ ಶ್ರೇಣಿಯಿಂದ ಬದಲಾಯಿಸುವುದು. ಈ ರಚನೆಯನ್ನು ಸಂಭಾವ್ಯ ಕಾರ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು ವಿಶ್ಲೇಷಿಸಬಹುದುಃ ± = 2n−N. ಮರುಗಾತ್ರಗೊಳಿಸುವ ಕಾರ್ಯತಂತ್ರವು ಯಾವಾಗಲೂ ಎ ಕನಿಷ್ಠ ಅರ್ಧ ತುಂಬಿರಲು ಕಾರಣವಾಗುವುದರಿಂದ, ಬಯಸಿದಂತೆ ಈ ಸಂಭಾವ್ಯ ಕಾರ್ಯವು ಯಾವಾಗಲೂ ಋಣಾತ್ಮಕವಾಗಿರುವುದಿಲ್ಲ. ಹೆಚ್ಚಳ-ಗಾತ್ರದ ಕಾರ್ಯಾಚರಣೆಯು ಮರುಗಾತ್ರದ ಕಾರ್ಯಾಚರಣೆಗೆ ಕಾರಣವಾಗದಿದ್ದಾಗ, 2 ರಿಂದ ಹೆಚ್ಚಾಗುತ್ತದೆ, ಇದು ಸ್ಥಿರವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಕಾರ್ಯಾಚರಣೆಯ ಸ್ಥಿರವಾದ ನೈಜ ಸಮಯ ಮತ್ತು ಸಾಮರ್ಥ್ಯದ ನಿರಂತರ ಹೆಚ್ಚಳವು ಈ ರೀತಿಯ ಕಾರ್ಯಾಚರಣೆಗೆ ಸ್ಥಿರವಾದ ಭೋಗ್ಯ ಸಮಯವನ್ನು ನೀಡಲು ಸಂಯೋಜಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಹೆಚ್ಚಳ-ಗಾತ್ರದ ಕಾರ್ಯಾಚರಣೆಯು ಮರುಗಾತ್ರವನ್ನು ಉಂಟುಮಾಡಿದಾಗ, ಮರುಗಾತ್ರದ ನಂತರ φನ ಸಂಭಾವ್ಯ ಮೌಲ್ಯವು ಶೂನ್ಯಕ್ಕೆ ಇಳಿಯುತ್ತದೆ. ಹೊಸ ಆಂತರಿಕ ಶ್ರೇಣಿಯನ್ನು ಎ ಅನ್ನು ನಿಯೋಜಿಸುವುದು ಮತ್ತು ಹಳೆಯ ಆಂತರಿಕ ಶ್ರೇಣಿಯಿಂದ ಹೊಸದಕ್ಕೆ ಎಲ್ಲಾ ಮೌಲ್ಯಗಳನ್ನು ನಕಲಿಸುವುದು ಒ (ಎನ್) ನೈಜ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಆದರೆ (ಅನುಪಾತದ ಸಿ ಸ್ಥಿರಾಂಕದ ಸೂಕ್ತ ಆಯ್ಕೆಯೊಂದಿಗೆ) ಸಂಭಾವ್ಯ ಕಾರ್ಯದಲ್ಲಿನ ಇಳಿಕೆಯಿಂದ ಇದನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ರದ್ದುಗೊಳಿಸಲಾಗುತ್ತದೆ, ಮತ್ತೆ ಕಾರ್ಯಾಚರಣೆಗೆ ಸ್ಥಿರವಾದ ಒಟ್ಟು ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ಬಿಡುತ್ತದೆ. ದತ್ತಾಂಶ ರಚನೆಯ ಇತರ ಕಾರ್ಯಾಚರಣೆಗಳು (ರಚನೆಯ ಗಾತ್ರವನ್ನು ಬದಲಾಯಿಸದೆ ರಚನೆಯ ಕೋಶಗಳನ್ನು ಓದುವುದು ಮತ್ತು ಬರೆಯುವುದು) ಸಂಭಾವ್ಯ ಕಾರ್ಯವು ಬದಲಾಗಲು ಕಾರಣವಾಗುವುದಿಲ್ಲ ಮತ್ತು ಅವುಗಳ ನೈಜ ಸಮಯದಂತೆಯೇ ಸ್ಥಿರವಾದ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಆದ್ದರಿಂದ, ಮರುಗಾತ್ರಗೊಳಿಸುವ ಕಾರ್ಯತಂತ್ರ ಮತ್ತು ಸಂಭಾವ್ಯ ಕಾರ್ಯದ ಈ ಆಯ್ಕೆಯೊಂದಿಗೆ, ಸಂಭಾವ್ಯ ವಿಧಾನವು ಎಲ್ಲಾ ಕ್ರಿಯಾತ್ಮಕ ರಚನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳು ಸ್ಥಿರವಾದ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತವೆ ಎಂಬುದನ್ನು ತೋರಿಸುತ್ತದೆ. ಇದನ್ನು ಪರಿಶೋಧಿಸಿದ ಸಮಯ ಮತ್ತು ಕಾರ್ಯಾಚರಣೆಗಳ ಅನುಕ್ರಮಗಳ ಮೇಲಿನ ನೈಜ ಸಮಯಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಅಸಮಾನತೆಯೊಂದಿಗೆ ಸಂಯೋಜಿಸುವುದರಿಂದ, ಕೆಲವು ಪ್ರತ್ಯೇಕ ಕಾರ್ಯಾಚರಣೆಗಳು ಸ್ವತಃ ಒಂದು ರೇಖೀಯ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು ಎಂಬ ಅಂಶದ ಹೊರತಾಗಿಯೂ, ಯಾವುದೇ n ಡೈನಾಮಿಕ್ ಅರೇ ಕಾರ್ಯಾಚರಣೆಗಳ ಅನುಕ್ರಮವು ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ O (n) ನೈಜ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂಬುದನ್ನು ಇದು ತೋರಿಸುತ್ತದೆ. ಕ್ರಿಯಾತ್ಮಕ ಶ್ರೇಣಿಯು ರಚನೆಯ ಗಾತ್ರವನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಮತ್ತು ಅದನ್ನು ಹೆಚ್ಚಿಸುವ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವಾಗ, ಸಂಭಾವ್ಯ ಕಾರ್ಯವು ಋಣಾತ್ಮಕವಾಗುವುದನ್ನು ತಡೆಯಲು ಅದನ್ನು ಮಾರ್ಪಡಿಸಬೇಕು. ಇದನ್ನು ಮಾಡಲು ಒಂದು ಮಾರ್ಗವೆಂದರೆ ಮೇಲಿನ ಸೂತ್ರವನ್ನು ಅದರ ಸಂಪೂರ್ಣ ಮೌಲ್ಯದಿಂದ ಬದಲಾಯಿಸುವುದು. ಬಹು-ಪಾಪ್ ಸ್ಟ್ಯಾಕ್ ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸುವ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಪರಿಗಣಿಸಿಃ ಪ್ರಾರಂಭಿಸಿ-ಖಾಲಿ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ರಚಿಸಿ. ಪುಶ್-ಸ್ಟ್ಯಾಕ್ನ ಮೇಲೆ ಒಂದೇ ಅಂಶವನ್ನು ಸೇರಿಸಿ, ಸ್ಟ್ಯಾಕ್ ಅನ್ನು 1 ರಿಂದ ವಿಸ್ತರಿಸಿ. ಪಾಪ್ (ಕೆ)-ಸ್ಟ್ಯಾಕ್ನ ಮೇಲ್ಭಾಗದಿಂದ ಕೆ ಅಂಶಗಳನ್ನು ತೆಗೆದುಹಾಕಿ, ಅಲ್ಲಿ ಕೆ ಪ್ರಸ್ತುತ ಸ್ಟ್ಯಾಕ್ ಗಾತ್ರಕ್ಕಿಂತ ಹೆಚ್ಚಿಲ್ಲ ಪಾಪ್ (ಕೆ) ಗೆ ಒ (ಕೆ) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ, ಆದರೆ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳು ಒ (1) ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತವೆ ಎಂದು ನಾವು ತೋರಿಸಲು ಬಯಸುತ್ತೇವೆ. ಈ ರಚನೆಯನ್ನು ಸಂಭಾವ್ಯ ಕಾರ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು ವಿಶ್ಲೇಷಿಸಬಹುದುಃ ± = ಅಂಶಗಳ-ಸ್ಟಾಕ್ನಲ್ಲಿರುವ ಸಂಖ್ಯೆ ಈ ಸಂಖ್ಯೆಯು ಯಾವಾಗಲೂ ಋಣಾತ್ಮಕವಲ್ಲದದ್ದಾಗಿರುತ್ತದೆ, ಅಗತ್ಯವಿರುವಂತೆ. ಪುಶ್ ಕಾರ್ಯಾಚರಣೆಯು ಸ್ಥಿರವಾದ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು φ ಅನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸುತ್ತದೆ, ಆದ್ದರಿಂದ ಅದರ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವು ಸ್ಥಿರವಾಗಿರುತ್ತದೆ. ಪಾಪ್ ಕಾರ್ಯಾಚರಣೆಯು O (k) ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಆದರೆ k ಯಿಂದ φ ಅನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ, ಆದ್ದರಿಂದ ಅದರ ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವೂ ಸಹ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ. m ಕಾರ್ಯಾಚರಣೆಗಳ ಯಾವುದೇ ಅನುಕ್ರಮವು ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ O (m) ನೈಜ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ಇದು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ. ಬೈನರಿ ಕೌಂಟರ್ ಬೈನರಿ ಸಂಖ್ಯೆಯಾಗಿ ಪ್ರತಿನಿಧಿಸುವ ಮತ್ತು ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸುವ ಕೌಂಟರ್ ಅನ್ನು ಪರಿಗಣಿಸಿಃ ಪ್ರಾರಂಭಿಸಿಃ 0 ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಕೌಂಟರ್ ಅನ್ನು ರಚಿಸಿ. ಇಂಕ್ಃ ಕೌಂಟರ್ಗೆ 1 ಅನ್ನು ಸೇರಿಸಿ. ಓದಿರಿಃ ಪ್ರಸ್ತುತ ಕೌಂಟರ್ ಮೌಲ್ಯವನ್ನು ಹಿಂತಿರುಗಿಸಿ. ಈ ಉದಾಹರಣೆಗಾಗಿ, ನಾವು ಟ್ರಾನ್ಸ್ಡಿಕೋಟೋಮಸ್ ಯಂತ್ರ ಮಾದರಿಯನ್ನು ಬಳಸುತ್ತಿಲ್ಲ, ಬದಲಿಗೆ ಏರಿಕೆಯಲ್ಲಿ ಪ್ರತಿ ಬಿಟ್ ಕಾರ್ಯಾಚರಣೆಗೆ ಒಂದು ಘಟಕದ ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ಇಂಕ್ ಒ (1) ಸಾಲ ಮರುಪಾವತಿ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ನಾವು ತೋರಿಸಲು ಬಯಸುತ್ತೇವೆ. ಈ ರಚನೆಯನ್ನು ಸಂಭಾವ್ಯ ಕಾರ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು ವಿಶ್ಲೇಷಿಸಬಹುದುಃ ± = ಬಿಟ್ಗಳ ಸಂಖ್ಯೆ-ಸಮಾನ-ಟು-1 = ಹ್ಯಾಮಿಂಗ್ ವೇಟ್ (ಕೌಂಟರ್) ಈ ಸಂಖ್ಯೆಯು ಯಾವಾಗಲೂ ಋಣಾತ್ಮಕವಾಗಿರುವುದಿಲ್ಲ ಮತ್ತು ಅಗತ್ಯವಿರುವಂತೆ 0 ರಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. ಒಂದು ಇಂಕ್ ಕಾರ್ಯಾಚರಣೆಯು ಕನಿಷ್ಠ ಗಮನಾರ್ಹವಾದ ಬಿಟ್ ಅನ್ನು ತಿರುಗಿಸುತ್ತದೆ. ನಂತರ, ಎಲ್ಎಸ್ಬಿಯನ್ನು 1 ರಿಂದ 0 ಕ್ಕೆ ತಿರುಗಿಸಿದರೆ, ಮುಂದಿನ ಬಿಟ್ ಅನ್ನು ಸಹ ತಿರುಗಿಸಲಾಗುತ್ತದೆ. ಅಂತಿಮವಾಗಿ ಒಂದು ಬಿಟ್ ಅನ್ನು 0 ರಿಂದ 1 ಕ್ಕೆ ತಿರುಗಿಸುವವರೆಗೆ ಇದು ಮುಂದುವರಿಯುತ್ತದೆ, ಆ ಸಮಯದಲ್ಲಿ ಫ್ಲಿಪ್ಪಿಂಗ್ ನಿಲ್ಲುತ್ತದೆ. ಕೌಂಟರ್ ಆರಂಭದಲ್ಲಿ k1 ಬಿಟ್ಗಳಲ್ಲಿ ಕೊನೆಗೊಂಡರೆ, ನಾವು ಒಟ್ಟು k + 1 ಬಿಟ್ಗಳನ್ನು ತಿರುಗಿಸುತ್ತೇವೆ, ನಿಜವಾದ ಸಮಯ k + 1 ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಸಂಭಾವ್ಯತೆಯನ್ನು k − 1 ರಿಂದ ಕಡಿಮೆ ಮಾಡುತ್ತೇವೆ, ಆದ್ದರಿಂದ ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯವು 2 ಆಗಿದೆ. ಆದ್ದರಿಂದ, ಎಂ. ಐ. ಎನ್. ಸಿ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ನಡೆಸುವ ನಿಜವಾದ ಸಮಯವು ಓ (ಎಂ) ಆಗಿದೆ. ಸಂಭಾವ್ಯ ಕಾರ್ಯ ವಿಧಾನವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಫಿಬೊನಾಚಿ ರಾಶಿಗಳನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ, ಇದು ಆದ್ಯತೆಯ ಸರಣಿಯ ಒಂದು ರೂಪವಾಗಿದೆ, ಇದರಲ್ಲಿ ವಸ್ತುವನ್ನು ತೆಗೆದುಹಾಕಲು ಲಾಗರಿಥಮಿಕ್ ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಇತರ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳು ಸ್ಥಿರವಾದ ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತವೆ. ಪ್ರತಿ ಕಾರ್ಯಾಚರಣೆಗೆ ಲಾಗರಿಥಮಿಕ್ ಅಮೋರ್ಟೈಸ್ಡ್ ಸಮಯದೊಂದಿಗೆ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಯ ಸ್ವಯಂ-ಹೊಂದಾಣಿಕೆಯ ರೂಪವಾದ ಸ್ಪ್ಲೇ ಮರಗಳನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಸಹ ಇದನ್ನು ಬಳಸಬಹುದು. ಕ್ರಮಾವಳಿಗಳ ಉಲ್ಲೇಖಗಳ ವಿಶ್ಲೇಷಣೆ