ಡೌಗ್ LLOYD: ಆದ್ದರಿಂದ CS50 ರಲ್ಲಿ ನಾವು ಕಲಿತ ಸಾರ್ಟಿಂಗ್ ಮತ್ತು ಸರ್ಚಿಂಗ್ ವಿವಿಧ ಕ್ರಮಾವಳಿಗಳು. ಮತ್ತು ಕೆಲವೊಮ್ಮೆ ಮಾಡಬಹುದು ಇರಿಸಿಕೊಳ್ಳಲು ಸ್ವಲ್ಪ ಟ್ರಿಕಿ ಏನು ಕ್ರಮಾವಳಿಯ ಟ್ರ್ಯಾಕ್ ಮಾಡುತ್ತದೆ. ನಾವು ನಿಜವಾಗಿಯೂ ಮಾತ್ರ ಬಂದಿದೆ ತುಂಬಾ ಮೇಲ್ಮೈ ತೆಗೆದ ಇತರ ಶೋಧನೆ ಇವೆ ಮತ್ತು ದತ್ತಾಂಶ ಜೋಡಣೆ ಕ್ರಮಾವಳಿಗಳು. ಆದ್ದರಿಂದ ಈ ವೀಡಿಯೊದಲ್ಲಿ ಹೊರಡೋಣ ಕೇವಲ ಕೆಲವು ನಿಮಿಷಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು ಪ್ರಯತ್ನಿಸಿ ಮತ್ತು ಪ್ರತಿ ಕ್ರಮಾವಳಿ ಗಿಸಿ ಅದರ ಕೋರ್ ಅಂಶಗಳನ್ನು ಕೆಳಗೆ ಆದ್ದರಿಂದ ನೀವು ಅತ್ಯಂತ ನೆನಪಿಸಿಕೊಳ್ಳಬಹುದಾದ ಬಗ್ಗೆ ಪ್ರಮುಖ ಮಾಹಿತಿ ಮತ್ತು ಅಭಿವ್ಯಕ್ತಿಗೊಳಿಸುವ ಸಾಧ್ಯವಾಗುತ್ತದೆ ವ್ಯತ್ಯಾಸಗಳು, ಅಗತ್ಯವಿದ್ದರೆ. 

ಮೊದಲ ಆಯ್ಕೆಯನ್ನು ತೆರನಾದ. ಆಯ್ಕೆ ರೀತಿಯ ಹಿಂದಿನ ಮೂಲ ಕಲ್ಪನೆಯನ್ನು ಚಿಕ್ಕ ಆಯ್ದ ಅಂಶ ಪಡೆಯುವ ಇದೆ ಮತ್ತು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಅದನ್ನು ಸ್ವ್ಯಾಪ್ ಎಂದು ರಚನೆಯ ಮೊದಲ ಆಯ್ದ ಅಂಶ. ನಾವು ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಹೇಳಿದರು ಆ ರನ್ ಬಾರಿ N ವರ್ಗ ಮಾಡಲಾಯಿತು. ಮತ್ತು ನೀವು ಏಕೆ ಮರುಪಡೆಯಲು ಬಯಸಿದರೆ, ತೆಗೆದುಕೊಳ್ಳಲು ಒಂದು ಆಯ್ಕೆ ರೀತಿಯ ವಿಡಿಯೋ ನೋಡಲು. ಉತ್ತಮ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ಸಹ ವರ್ಗ n ಇದೆ. 

ಬಬಲ್ ರೀತಿಯ, ಹಿಂದೆ ಕಲ್ಪನೆಯನ್ನು ಒಂದು ಪಕ್ಕದ ಜೋಡಿ ವಿನಿಮಯ ಮಾಡುವುದು. ಆದ್ದರಿಂದ ನೀವು ಸಹಾಯ ಮಾಡುತ್ತದೆ ಪ್ರಮುಖ ಇಲ್ಲಿದೆ ಇಲ್ಲಿ ವ್ಯತ್ಯಾಸ ಮರೆಯದಿರಿ. ಆಯ್ಕೆಯನ್ನು ತೆರನಾದ, ಇಲ್ಲಿಯವರೆಗೆ, ಚಿಕ್ಕ ಗುಳ್ಳೆ ಹೇಗೆ ರೀತಿಯ ಏನು ಪಕ್ಕದ ಜೋಡಿ ವಿನಿಮಯ. ನಾವು ಪಕ್ಕದ ಜೋಡಿ ವಿನಿಮಯ ಅಂಶಗಳನ್ನು ಅವರು ವೇಳೆ ಇದು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಆದೇಶ ಭರ್ತಿಯಾಗಿದೆ , ಬಲಕ್ಕೆ ದೊಡ್ಡ ಅಂಶಗಳನ್ನು ಗುಳ್ಳೆಗಳು ಮತ್ತು ಅದೇ ಸಮಯದಲ್ಲಿ ಇದು ಆರಂಭವಾಗುತ್ತದೆ ಎಡಕ್ಕೆ ಸಣ್ಣ ಅಂಶಗಳನ್ನು ಸರಿಸಲು. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ಬಬಲ್ ರೀತಿಯ ವರ್ಗ n ಇದೆ. ಉತ್ತಮ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ಬಬಲ್ ರೀತಿಯ n ಇದೆ. ಏಕೆಂದರೆ ಆ ಸನ್ನಿವೇಶದಲ್ಲಿ ನಾವು ವಾಸ್ತವವಾಗಿ ಇಲ್ಲ ನಾವು ಅವಶ್ಯಕತೆ ಇರಬಹುದು ಎಲ್ಲಾ ಯಾವುದೇ ವಿನಿಮಯ. ನಾವು ಕೇವಲ ಒಂದು ಮಾಡಬೇಕು ಎಲ್ಲಾ N ಅಂಶಗಳನ್ನು ಅಡ್ಡಲಾಗಿ ಹಾದು. 

ಅಳವಡಿಕೆಯ ರೀತಿಯ ರಲ್ಲಿ ಇಲ್ಲಿ ಮೂಲ ಕಲ್ಪನೆಯನ್ನು ಬದಲಾಯಿತು. ಎಂದು, ಅಳವಡಿಕೆಯ ರೀತಿಯ ಕೀವರ್ಡ್ ಇಲ್ಲಿದೆ. ನಾವು ಮೂಲಕ ಒಮ್ಮೆ ಹೆಜ್ಜೆ ನೀನು ರಚನೆಯ ಎಡದಿಂದ ಬಲಕ್ಕೆ. ನಾವು ಏನು ಎಂದು, ನಾವು ಆರ್ ಅಂಶಗಳ ಬದಲಾಗುವ ಹೋಗುವ ನಾವು ಈಗಾಗಲೇ ಕೊಠಡಿ ಮಾಡಲು ನೋಡಿದ ಎಲ್ಲೋ ಹೊಂದಿಕೊಳ್ಳಲು ಅಗತ್ಯವಿರುವ ಸಣ್ಣದಾಗಿ ಆ ವಿಂಗಡಿಸಲಾದ ಭಾಗವನ್ನು. ನಾವು ವಿಂಗಡಿಸಲಾದ ಸರಣಿ ನಿರ್ಮಿಸಲು ಒಂದು ಎಡದಿಂದ ಬಲಕ್ಕೆ ಒಂದು ಸಮಯದಲ್ಲಿ ಅಂಶ, ಮತ್ತು ನಾವು ಕೊಠಡಿ ಮಾಡಲು ವಿಷಯಗಳನ್ನು ರಜೆ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ಅಳವಡಿಕೆಯ ರೀತಿಯ ವರ್ಗ n ಇದೆ. ಉತ್ತಮ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ n ಇದೆ. 

ಕೀವರ್ಡ್ sort-- ವಿಲೀನಗೊಳಿಸಿ ಇಲ್ಲಿ ಬೇರ್ಪಟ್ಟು ವಿಲೀನಗೊಳ್ಳಲು ಇದೆ. ನಾವು ಎಂದು, ಪೂರ್ಣ ರಚನೆಯ ವಿಭಜನೆಯಾಯಿತು ಇದು ಆರು ಅಂಶಗಳನ್ನು ಎಂಟು ಅಂಶಗಳನ್ನು, 10,000 ಅಂಶಗಳನ್ನು ನಾವು ಬೇರ್ಪಟ್ಟು ಕೆಳಗೆ ಅರ್ಧ ಮೂಲಕ ಅರ್ಧ ಮೂಲಕ ಅರ್ಧ ಮೂಲಕ ನಾವು ರಚನೆಯ ಅಡಿಯಲ್ಲಿ ತನಕ ಎನ್ ಒಂದು ಅಂಶ ಆಯ್ರೆಗಳ. ಎನ್ ಒಂದು ಅಂಶ ಆಯ್ರೆಗಳ ಸೆಟ್. ನಾವು ಒಂದು ಪ್ರಾರಂಭವಾಯಿತು 1,000 ಅಂಶ ರಚನೆಯ, ಮತ್ತು ನಾವು ಅಂಕ ಪಡೆಯಲು ಅಲ್ಲಿ ನಾವು 1,000 ಒಂದು ಅಂಶ ಸರಣಿಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ನಂತರ ನಾವು ಆ ಉಪ ರಚನೆಗಳು ವಿಲೀನಗೊಳ್ಳಲು ಆರಂಭಿಸಲು ಮತ್ತೆ ಒಟ್ಟಿಗೆ ಸರಿಯಾದ ಕ್ರಮದಲ್ಲಿ. ನಾವು ಎರಡು ಒಂದು ಅಂಶ ರಚನೆಗಳು ತೆಗೆದುಕೊಳ್ಳಲು ಮತ್ತು ಎರಡು ಅಂಶ ರಚನೆಯ ರಚಿಸಲು. ನಾವು ಎರಡು ಎರಡು ಅಂಶ ರಚನೆಗಳು ತೆಗೆದುಕೊಳ್ಳಲು ಮತ್ತು ನಾಲ್ಕು ಅಂಶ ರಚನೆಯ ರಚಿಸಲು ಹೀಗೆ ಹೀಗೆ ನಾವು ಮಾಡಿದ ರವರೆಗೆ ಮತ್ತೆ ಒಂದು ಎನ್ ಅಂಶ ರಚನೆಯ ಮರುನಿರ್ಮಿಸಲಾಯಿತು. 

ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ವಿಲೀನ ರೀತಿಯ N ಬಾರಿ ಲಾಗ್ ಎನ್. ನಾವು N ಅಂಶಗಳನ್ನು ಹೊಂದಿವೆ, ಆದರೆ ಈ ಪುನರ್ಸಂಯೋಜಿಸಿದ ಪ್ರಕ್ರಿಯೆ ಲಾಗ್ N ಕ್ರಮಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಪಡೆಯಲು ಪೂರ್ಣ ಶ್ರೇಣಿಯನ್ನು ಬ್ಯಾಕ್. ಸಮಯ ಔಟ್ ಅತ್ಯುತ್ತಮ ಪ್ರಕರಣವು ಸೂಚನೆ ಪ್ರವೇಶಿಸಲು ಎನ್ ಈ ಪ್ರಕ್ರಿಯೆ ನಿಜವಾಗಿಯೂ ಏಕೆಂದರೆ ಶ್ರೇಣಿಯನ್ನು ಎಂದು ಕಾಳಜಿ ವಿಂಗಡಿಸುತ್ತದೆ ಅಥವಾ ಆರಂಭವಾಗಬೇಕು. ಪ್ರಕ್ರಿಯೆ ಇತ್ತು, ಒಂದೇ ಶಾರ್ಟ್ ಸರ್ಕ್ಯೂಟ್ ವಿಷಯಗಳಿಗೆ ಯಾವುದೇ ರೀತಿಯಲ್ಲಿ. ಆದ್ದರಿಂದ N ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ N ಲಾಗ್, ಎನ್ ಅತ್ಯುತ್ತಮ ಸಂದರ್ಭದಲ್ಲಿ N ಲಾಗ್. 

ನಾವು ಎರಡು ಕುರಿತು ಕ್ರಮಾವಳಿಗಳು ಹುಡುಕುವ. ಆದ್ದರಿಂದ ರೇಖೀಯ ಹುಡುಕಾಟ iterating ಸುಮಾರು. ನಾವು ರಚನೆಯ ಸುತ್ತಲೂ ಮುಂದುವರೆಯಲು ಒಮ್ಮೆ ಎಡದಿಂದ ಬಲಕ್ಕೆ, ಸಂಖ್ಯೆ ಪಡೆಯುವ ಪ್ರಯತ್ನ ಎಂದು ನಾವು ಹುಡುಕುತ್ತಿರುವ. ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ n ನ ದೊಡ್ಡ ಒ ಆಗಿದೆ. ಇದು iterating ನಮಗೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದು ಪ್ರತಿಯೊಂದು ಅಂಶ ಅಡ್ಡಲಾಗಿ ನಾವು ಹುಡುಕುತ್ತಿರುವ ಅಂಶ ಪಡೆಯುವ ಎರಡೂ, ಕೊನೆಯ ಸ್ಥಾನ, ಅಥವಾ ಇಲ್ಲ. ಆದರೆ ನಾವು ರವರೆಗೆ ದೃಢೀಕರಿಸಿ ಸಾಧ್ಯವಿಲ್ಲ ನಾವು ಎಲ್ಲವನ್ನೂ ನೋಡಿದ್ದಾರೆ ಬಂದಿದೆ. ಉತ್ತಮ ಸಂದರ್ಭದಲ್ಲಿ ನಾನು, ನಾವು ತಕ್ಷಣ ಹೇಗೆ. ಅತ್ಯುತ್ತಮ ಕೇಸ್ ರನ್ ಸಮಯ ರೇಖೀಯ ಹುಡುಕಾಟ 1 ಒಮೆಗಾ ಹೊಂದಿದೆ. 

ಕೊನೆಯದಾಗಿ, ಬೈನರಿ ಸರ್ಚ್, ಇತ್ತು ಇದು ಬಗೆಬಗೆಯ ಶ್ರೇಣಿಯನ್ನು ಅಗತ್ಯವಿದೆ. ಒಂದು ನೆನಪಿಡಿ ಪ್ರಮುಖ ಪರಿಗಣಿಸಿ ಬೈನರಿ ಸರ್ಚ್ ಕೆಲಸ ಮಾಡುವಾಗ. ಇದು ಅದನ್ನು ಬಳಸಿಕೊಂಡು ಒಂದು ಪೂರ್ವಾಪೇಕ್ಷಿತ ಇಲ್ಲಿದೆ ನೀವು ಮೂಲಕ ಹುಡುಕುತ್ತಿರುವ ರಚನೆಯ ಬೇರ್ಪಡಿಸಬೇಕು. ಇಲ್ಲದಿದ್ದರೆ, ಕೀವರ್ಡ್ ವಿಂಗಡಿಸಿ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳಲು ಆಗಿದೆ. ಅರ್ಧದಷ್ಟನ್ನು ರಚನೆಯ ವಿಭಜನೆಯಾಯಿತು ಮತ್ತು ಅಂಶಗಳನ್ನು ಅರ್ಧ ತೊಡೆದುಹಾಕಲು ಪ್ರತಿ ಬಾರಿ ನೀವು ಮೂಲಕ ಮುಂದುವರೆಯಲು. ಈ ವಿಭಜನೆಯನ್ನು ವಶಪಡಿಸಿಕೊಳ್ಳಲು ಮತ್ತು ಅರ್ಧ ವಿಧಾನದಲ್ಲಿ ವಿಭಜಿಸುವ ವಿಷಯಗಳನ್ನು ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ಆಫ್ ಬೈನರಿ ಸರ್ಚ್ ಗಣನೀಯವಾಗಿ ಇದು N ಲಾಗ್ ರೇಖೀಯ ಹುಡುಕಾಟ N ಉತ್ತಮ. ಉತ್ತಮ ಸಂದರ್ಭದಲ್ಲಿ ರನ್ ಸಮಯ ಇನ್ನೂ ಒಂದು. 

ನಾವು ತಕ್ಷಣ ಅದನ್ನು ಅನಿಸಬಹುದು ಮೊದಲ ಬಾರಿಗೆ ನಾವು, ಒಂದು ವಿಭಾಗ, ಆದರೆ ಮತ್ತೆ, ನೆನಪು ಬೈನರಿ ಸರ್ಚ್ ಆದರೂ ರೇಖೀಯ ಹುಡುಕಾಟ ಗಣನೀಯವಾಗಿ ಉತ್ತಮ ಲಾಗ್ ಎಂಬ ಕಾರಣದಿಂದ ಎನ್ ವಿರುದ್ಧ, ನೀವು ಕೆಲಸದ ಮೂಲಕ ಹೋಗಬೇಕಾಗಬಹುದು ಮೊದಲ ನಿಮ್ಮ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುವ ಯಾವ ಅವಲಂಬಿಸಿ ಅದು ಕಡಿಮೆ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಲು ಇರಬಹುದು ವಿಂಗಡಿಸುತ್ತದೆ iterating ಗಾತ್ರವನ್ನು. 

ನಾನು ಡೌಗ್ ಲಾಯ್ಡ್ ಮನುಷ್ಯ, ಈ CS50 ಹೊಂದಿದೆ.