A Number Of Algorithm Complexity Analysis

There have been two ways to analysis the quality of an algorithm (1)worst case analysis and, (2) average case analysis. Worst case analysispresents the complexity bound of an algorithm corresponding to its certainbad input instance. If a bad input instance of an algorithm is less plausiblein practice, it is improper to describe the behavior of an algorithm in practiceby using worst case analysis only. In addition, Average case analysis needto presume a probability distribution over the input instances space of analgorithm in advance. However, such probability distribution over the inputinstances space either does not exist or may be hard to de?ne in practice.In this case, it isn't convincible to describe the behavior of an algorithm inpractice by using average case analysis. Spielman and Teng proposed anotheranalysis method named smoothed analysis of algorithms. Smoothed analysisis di?erent from worst case analysis and average case analysis. In this anal-ysis, input is considered to be perturbed by noise(ex. Gaussian noise of verysmall variance) and is fed to the algorithms taking real inputs. Therefore,the complexity of an algorithm in smoothed analysis relates to the input sizeand the perturbation magnitude and is expressed as a function of the inputsize and the perturbation magnitude. Intuitively, smoothed complexity is themaximum over instances of the expected complexity in a neighborhood of aninstance. Since most real world problems are generated from data that isinherently noisy, if the random perturbation model considered in smoothedanalysis is geared to actual computing circumstances, smoothed analysis will IVdescribe the performance of an algorithm in practice more reasonable in the-ory. In this research, the analysis of several algorithms are studied, the resultsare presented as following: 1. In this research, the smoothed analysis of the condition numbers ofmatrices and the smoothed precision of bits needed to perform Gaussian elim-ination under Gaussian random perturbation model are studied deeply. Byusing the two inequalities presented in this research, the smoothed analysisof condition number of matrix performed by Sankar et al. in [1] is simpli?ed,and the conjecture on improving the smoothed bound of the condition num-ber of matrix is partial solved. The smoothed complexity of precision of bitsneeded to perform Gaussian elimination is improved also. 2. In this research, the smoothed analysis of the condition numbers ofsymmetric matrices and the smoothed precision of bits needed to performGaussian elimination under zero-preserving Gaussian random perturbationmodel are studied deeply. By using the two inequalities presented in thisresearch, the smoothed analysis of condition number of symmetric matrixperformed by Sankar et al. in [1] is simpli?ed, and the conjecture on improv-ing the smoothed bound of the condition number of matrix is partial solved.The smoothed analysis of precision of bits needed to perform Gaussian elim-ination with symmetric coe?cients matrix is performed corresponding topre-simpli?ed and post-simpli?ed respectively. 3. In this research, a random perturbation model named TSSP-Modelis described from a practical application of Quick-sorting. It is used in thesmoothed analysis of the algorithms like Quick-sorting, whose performancesare mainly determined by the initial order of the elements of an instance. Asmoothed analysis of Quick-sorting under TSSP-Model is performed and thesmoothed time complexity of Quick-sorting is presented as O(λn · log(n)), 2where λ be the random perturbation magnitude. 4. In this research, the problem of scheduling jobs arriving over time Vin parallel machines setting, with immediate dispatching, allowing preemp-tions while disallowing migration of jobs that have been scheduled on one...