Journal articles: '080201 Analysis of Algorithms and Complexity'

1

Hower, Walter. "Constraint satisfaction — Algorithms and complexity analysis." Information Processing Letters 55, no. 3 (August 1995): 171–78. http://dx.doi.org/10.1016/0020-0190(95)00089-u.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

BARMAK, OLEXANDER, PAVLO RADIUK, MARYNA MOLCHANOVA, and OLENA SOBKO. "APPROACHES TO PRACTICAL ANALYSIS OF COMPUTING ALGORITHMS." Herald of Khmelnytskyi National University 303, no. 6 (December 2021): 102–5. http://dx.doi.org/10.31891/2307-5732-2021-303-6-102-105.

Full text

Abstract:

The present work proposes a practical approach to determining the main types of algorithms, depending on their effectiveness in the appearance of the software code. Examples of analysis of the software code for computational complexity are given in the order of reducing the efficiency supplied as (in asymptotic designations): O(1), O(LogN), O(N), O(NlogN), O(N2), O(N2), O(N2), O(N3). The research task was to analyze the software code and specific conditions in which the algorithm refers to a particular type of computational complexity. The aim of analyzing the complexity of algorithms is to find the optimal algorithm for solving a specific problem. The criterion of optimality of the algorithm is chosen by the complexity of the algorithm, i.e., the number of elementary operations that must be performed to solve the problem using this algorithm. The complexity function is the ratio that connects the algorithm’s input data with the number of elementary operations. The paper contains a description of classical computational complexity that can be revealed by visual analysis of program code. The main types of computational complexity are (listed in descending order of efficiency) constant, logarithmic, linear, linear-logarithmic, quadratic, cubic. Also, methods for the determination of computational complexity are described. It is established that the main factors that can assess the algorithm’s computational complexity for the visual analysis of the software code are the presence of cycles, especially enclosed, reversibility of the algorithm, etc. Further research could usefully explore a method of semantic analysis of program code to predict the assessment of its computational complexity.

APA, Harvard, Vancouver, ISO, and other styles

3

Chen, Xinjia, Kemin Zhou, and Jorge Aravena. "Probabilistic Robustness Analysis—Risks, Complexity, and Algorithms." SIAM Journal on Control and Optimization 47, no. 5 (January 2008): 2693–723. http://dx.doi.org/10.1137/060668407.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Hagiya, Masami, John A. Rose, Ken Komiya, and Kensaku Sakamoto. "Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms." Theoretical Computer Science 287, no. 1 (September 2002): 59–71. http://dx.doi.org/10.1016/s0304-3975(02)00095-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Faran, Rachel, and Orna Kupferman. "A Parametrized Analysis of Algorithms on Hierarchical Graphs." International Journal of Foundations of Computer Science 30, no. 06n07 (September 2019): 979–1003. http://dx.doi.org/10.1142/s0129054119400252.

Full text

Abstract:

Hierarchical graphs are used in order to describe systems with a sequential composition of sub-systems. A hierarchical graph consists of a vector of subgraphs. Vertices in a subgraph may “call” other subgraphs. The reuse of subgraphs, possibly in a nested way, causes hierarchical graphs to be exponentially more succinct than equivalent flat graphs. Early research on hierarchical graphs and the computational price of their succinctness suggests that there is no strong correlation between the complexity of problems when applied to flat graphs and their complexity in the hierarchical setting. That is, the complexity in the hierarchical setting is higher, but all “jumps” in complexity up to an exponential one are exhibited, including no jumps in some problems. We continue the study of the complexity of algorithms for hierarchical graphs, with the following contributions: (1) In many applications, the subgraphs have a small, often a constant, number of exit vertices, namely vertices from which control returns to the calling subgraph. We offer a parameterized analysis of the complexity and point to problems where the complexity becomes lower when the number of exit vertices is bounded by a constant. (2) We describe a general methodology for algorithms on hierarchical graphs. The methodology is based on an iterative compression of subgraphs in a way that maintains the solution to the problems and results in subgraphs whose size depends only on the number of exit vertices, and (3) we handle labeled hierarchical graphs, where edges are labeled by letters from some alphabet, and the problems refer to the languages of the graphs.

APA, Harvard, Vancouver, ISO, and other styles

6

Douglas, B. L., and J. B. Wang. "Complexity Analysis of Quantum Walk Based Search Algorithms." Journal of Computational and Theoretical Nanoscience 10, no. 7 (July 1, 2013): 1601–5. http://dx.doi.org/10.1166/jctn.2013.3095.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Lin, M. S., M. S. Chang, and D. J. Chen. "Distributed-program reliability analysis: complexity and efficient algorithms." IEEE Transactions on Reliability 48, no. 1 (March 1999): 87–95. http://dx.doi.org/10.1109/24.765932.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Zakarauskas, P., and J. M. Ozard. "Complexity analysis for partitioning nearest neighbor searching algorithms." IEEE Transactions on Pattern Analysis and Machine Intelligence 18, no. 6 (June 1996): 663–68. http://dx.doi.org/10.1109/34.506419.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Barik, Somsubhra, and Haris Vikalo. "Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis." IEEE Transactions on Signal Processing 62, no. 9 (May 2014): 2212–25. http://dx.doi.org/10.1109/tsp.2014.2307836.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Jiang, Tao, Ming Li, and Paul M. B. Vitányi. "Average-case analysis of algorithms using Kolmogorov complexity." Journal of Computer Science and Technology 15, no. 5 (September 2000): 402–8. http://dx.doi.org/10.1007/bf02950402.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Cohen, Edith, and Nimrod Megiddo. "Algorithms and complexity analysis for some flow problems." Algorithmica 11, no. 3 (March 1994): 320–40. http://dx.doi.org/10.1007/bf01240739.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Ibarra, Oscar H., Pedro C. Diniz, and Martin C. Rinard. "On the Complexity of Commutativity Analysis." International Journal of Foundations of Computer Science 08, no. 01 (March 1997): 81–94. http://dx.doi.org/10.1142/s0129054197000069.

Full text

Abstract:

Two operations commute if they generate the same result regardless of the order in which they execute. Commutativity is an important property — commuting operations enable significant optimizations in the fields of parallel computing, optimizing compilers, parallelizing compilers and database concurrency control. Algorithms that statically decide if operations commute can be an important component of systems in these fields because they enable the automatic application of these optimizations. In this paper we define the commutativity decision problem and establish its complexity for a variety of basic instructions and control constructs. Although deciding commutativity is, in general, undecidable or computationally intractable, we believe that efficient algorithms exist that can solve many of the cases that arise in practice.

APA, Harvard, Vancouver, ISO, and other styles

13

Gohberg, I., T. Kailath, and I. Koltracht. "Linear complexity algorithms for semiseparable matrices." Integral Equations and Operator Theory 8, no. 6 (November 1985): 780–804. http://dx.doi.org/10.1007/bf01213791.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Chandrasekaran, M., P. Sriramya, B. Parvathavarthini, and M. Saravanamanikandan. "Computational Complexity Analysis of Selective Breeding Algorithm." Applied Mechanics and Materials 591 (July 2014): 172–75. http://dx.doi.org/10.4028/www.scientific.net/amm.591.172.

Full text

Abstract:

In modern years, there has been growing importance in the design, analysis and to resolve extremely complex problems. Because of the complexity of problem variants and the difficult nature of the problems they deal with, it is arguably impracticable in the majority time to build appropriate guarantees about the number of fitness evaluations needed for an algorithm to and an optimal solution. In such situations, heuristic algorithms can solve approximate solutions; however suitable time and space complication take part an important role. In present, all recognized algorithms for NP-complete problems are requiring time that's exponential within the problem size. The acknowledged NP-hardness results imply that for several combinatorial optimization problems there are no efficient algorithms that realize a best resolution, or maybe a close to best resolution, on each instance. The study Computational Complexity Analysis of Selective Breeding algorithm involves both an algorithmic issue and a theoretical challenge and the excellence of a heuristic.

APA, Harvard, Vancouver, ISO, and other styles

15

B, Sarada, Vinayaka Murthy. M, and Udaya Rani. V. "Analysis of large volume data processing using clustering algorithms." International Journal of Engineering & Technology 7, no. 4.5 (September 22, 2018): 685. http://dx.doi.org/10.14419/ijet.v7i4.5.25058.

Full text

Abstract:

The study of large dataset with velocity, variety and volume which is also known as Big data. When the dataset has limited number of clusters, low dimensions and small number of data points the existing traditional clustering algorithms can be used.. As we know this is the internet age, the data is growing very fast and existing clustering algorithms are not giving the acceptable results in terms of time complexity and spatial complexity. So there is a need to develop a new approach of applying clustering of large volume of data processing with low time and spatial complexity through MapReduce and Hadoop frame work applying to different clustering algorithms, k-means, Canopy clustering and proposed algorithm .The analysis shows that the large volume of data processing will take low time and spatial complexity when compared to small volume of data.

APA, Harvard, Vancouver, ISO, and other styles

16

Shrawankar, Urmila, and Krutika Jayant Sapkal. "Complexity Analysis of Vedic Mathematics Algorithms for Multicore Environment." International Journal of Rough Sets and Data Analysis 4, no. 4 (October 2017): 31–47. http://dx.doi.org/10.4018/ijrsda.2017100103.

Full text

Abstract:

The huge computations performed sequentially requires a lot of time for execution as on contrary to the concurrent implementation. Many problems are involved in the dense linear algebra operations the main focus for this work is for solving linear equations. The problem of solving linear equations when approached using parallel implementation will yield better results. The Vedic mathematical method of Paravartya Yojayet is having less complexity as compared to the conventional methods. This work mainly focuses on the parallel implementation of the Paravartya Yojayet and its comparison to the benchmarking of the existing LU decomposition. The results of this implementation of Paravartya Yojayet are better when analysed theoretically but its actual parallel implementation will vary so it needs to be analysed and this work presents the same. The comparative analysis of the two ways for parallelization of the Paravartya Yojayet methods viz. ‘For loop' parallelization and the ‘direct parallelization' is also analysed in this work.

APA, Harvard, Vancouver, ISO, and other styles

17

He, Jun, and Xin Yao. "Drift analysis and average time complexity of evolutionary algorithms." Artificial Intelligence 127, no. 1 (March 2001): 57–85. http://dx.doi.org/10.1016/s0004-3702(01)00058-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Peng, Chao, Jie Zhou, Binhai Zhu, and Hong Zhu. "Complexity analysis and algorithms for the Program Download Problem." Journal of Combinatorial Optimization 29, no. 1 (February 4, 2014): 216–27. http://dx.doi.org/10.1007/s10878-013-9702-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Phan, Anh-Huy, Petr Tichavský, and Andrzej Cichocki. "Low Complexity Damped Gauss--Newton Algorithms for CANDECOMP/PARAFAC." SIAM Journal on Matrix Analysis and Applications 34, no. 1 (January 2013): 126–47. http://dx.doi.org/10.1137/100808034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Giménez, Nardo, Joos Heintz, Guillermo Matera, and Pablo Solernó. "Lower complexity bounds for interpolation algorithms." Journal of Complexity 27, no. 2 (April 2011): 151–87. http://dx.doi.org/10.1016/j.jco.2010.10.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Okada, Hugo Kenji Rodrigues, Andre Ricardo Nascimento das Neves, and Ricardo Shitsuka. "Analysis of Decision Tree Induction Algorithms." Research, Society and Development 8, no. 11 (August 24, 2019): e298111473. http://dx.doi.org/10.33448/rsd-v8i11.1473.

Full text

Abstract:

Decision trees are data structures or computational methods that enable nonparametric supervised machine learning and are used in classification and regression tasks. The aim of this paper is to present a comparison between the decision tree induction algorithms C4.5 and CART. A quantitative study is performed in which the two methods are compared by analyzing the following aspects: operation and complexity. The experiments presented practically equal hit percentages in the execution time for tree induction, however, the CART algorithm was approximately 46.24% slower than C4.5 and was considered to be more effective.

APA, Harvard, Vancouver, ISO, and other styles

22

Semenets, Valerii, O. S. Marukhnenko, I. D. Gorbenko, and G. Z. Khalimov. "Comparative analysis of one-time hash-based signatures." Radiotekhnika, no. 203 (December 23, 2020): 5–18. http://dx.doi.org/10.30837/rt.2020.4.203.01.

Full text

Abstract:

Hash-based signatures are a wide class of post-quantum cryptographic algorithms, their security is based on the complexity of collision and preimage search problems for cryptographic hash functions. The main advantages of this class are post-quantization, easy modification and a well-researched mathematical base. The disadvantages are large sizes of signatures and limited number of uses of one key pair. The most promising algorithms of this class include algorithms of the SPHINCS type, which have a complex structure, including, among others, a one-time Winternitz signature. The paper analyzes the existing one-time signature algorithms, both well-known Lamport and Winternitz schemes, taking into account modifications of the latter one, and alternative methods. An analysis of the security of modified algorithms has been shown, which showed that their security is based on the same mathematical basis as the security of the original algorithms. The one-time use requirement remains critical to the safety of each of the algorithms studied. The sizes of keys and signatures and computational complexity of various algorithms are compared, in what their basic differences consist. The modified algorithms do not add fundamentally new components in cryptosystems but they make it possible to achieve a certain optimization, shifting the conditions of space-time compromise. The extended Lamport signature is of a particular interest, having the same computational complexity and key sizes as the original algorithm, and at the same time allowing one to halve the signature size. In the context of the SPHINCS cryptosystem, the Winternitz signature remains the best option, since it allows the complete computation of the public key directly from the signature.

APA, Harvard, Vancouver, ISO, and other styles

23

Allan de Oliveira Veras, Adonney. "Complexity analysis of algorithms: A case study on bioinformatics tools." World Journal of Biology and Biotechnology 6, no. 3 (October 3, 2021): 11. http://dx.doi.org/10.33865/wjb.006.03.0445.

Full text

Abstract:

The data volume produced by the omic sciences nowadays was driven by the adoption of new generation sequencing platforms, popularly called NGS (Next Generation Sequencing). Among the analysis performed with this data, we can mention: mapping, genome assembly, genome annotation, pangenomic analysis, quality control, redundancy removal, among others. When it comes to redundancy removal analysis, it is worth noting the existence of several tools that perform this task, with proven accuracy through their scientific publications, but they lack criteria related to algorithmic complexity. Thus, this work aims to perform an algorithmic complexity analysis in computational tools for removing redundancy of raw reads from the DNA sequencing process, through empirical analysis. The analysis was performed with sixteen raw reads datasets. The datasets were processed with the following tools: MarDRe, NGSReadsTreatment, ParDRe, FastUniq, and BioSeqZip, and analyzed using the R statistical platform, through the GuessCompx package. The results demonstrate that the BioSeqZip and ParDRe tools present less complexity in this analysis

APA, Harvard, Vancouver, ISO, and other styles

24

Pasqualetti, Fabio, Antonio Franchi, and Francesco Bullo. "On Cooperative Patrolling: Optimal Trajectories, Complexity Analysis, and Approximation Algorithms." IEEE Transactions on Robotics 28, no. 3 (June 2012): 592–606. http://dx.doi.org/10.1109/tro.2011.2179580.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Litvinov, G. L. "Idempotent and tropical mathematics; complexity of algorithms and interval analysis." Computers & Mathematics with Applications 65, no. 10 (May 2013): 1483–96. http://dx.doi.org/10.1016/j.camwa.2012.09.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Tadayon, Bita, and J. Cole Smith. "Algorithms and Complexity Analysis for Robust Single-Machine Scheduling Problems." Journal of Scheduling 18, no. 6 (February 6, 2015): 575–92. http://dx.doi.org/10.1007/s10951-015-0418-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Vinokur, A. B., and G. P. Kozhevnikova. "Complexity analysis of algorithms by recognition of their classification properties." Cybernetics and Systems Analysis 27, no. 6 (November 1991): 840–52. http://dx.doi.org/10.1007/bf01246515.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Karaman, Ayşe, and Hossam Hassanein. "Core-selection algorithms in multicast routing - comparative and complexity analysis." Computer Communications 29, no. 8 (May 2006): 998–1014. http://dx.doi.org/10.1016/j.comcom.2005.06.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Gaviano, M., and D. Lera. "A Complexity Analysis of Local Search Algorithms in Global Optimization." Optimization Methods and Software 17, no. 1 (January 2002): 113–27. http://dx.doi.org/10.1080/10556780290027783.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Rapine, Christophe, Guillaume Goisque, and Ayse Akbalik. "Energy-aware lot sizing problem: Complexity analysis and exact algorithms." International Journal of Production Economics 203 (September 2018): 254–63. http://dx.doi.org/10.1016/j.ijpe.2018.06.020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Winograd, Joseph M., and S. Hamid Nawab. "Probabilistic complexity analysis for a class of approximate DFT algorithms." Journal of VLSI signal processing systems for signal, image and video technology 14, no. 2 (November 1996): 193–205. http://dx.doi.org/10.1007/bf00925499.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Thameri, Messaoud, Karim Abed-Meraim, and Adel Belouchrani. "Low complexity adaptive algorithms for Principal and Minor Component Analysis." Digital Signal Processing 23, no. 1 (January 2013): 19–29. http://dx.doi.org/10.1016/j.dsp.2012.09.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Kohli, Rajeev, and Ramesh Krishnamurti. "Optimal product design using conjoint analysis: Computational complexity and algorithms." European Journal of Operational Research 40, no. 2 (May 1989): 186–95. http://dx.doi.org/10.1016/0377-2217(89)90329-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Jiang, Bo, Tianyi Lin, Shiqian Ma, and Shuzhong Zhang. "Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis." Computational Optimization and Applications 72, no. 1 (September 25, 2018): 115–57. http://dx.doi.org/10.1007/s10589-018-0034-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Ma, Hang. "Extended Abstract: A Competitive Analysis of Online Multi-Agent Path Finding." Proceedings of the International Symposium on Combinatorial Search 12, no. 1 (July 21, 2021): 182–84. http://dx.doi.org/10.1609/socs.v12i1.18577.

Full text

Abstract:

This is an extended abstract of a paper to be published at ICAPS 2021. We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories. We present several complexity and competitiveness results for online MAPF and its algorithms, which provides theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.

APA, Harvard, Vancouver, ISO, and other styles

36

Olver, Sheehan, Richard Mikaël Slevinsky, and Alex Townsend. "Fast algorithms using orthogonal polynomials." Acta Numerica 29 (May 2020): 573–699. http://dx.doi.org/10.1017/s0962492920000045.

Full text

Abstract:

We review recent advances in algorithms for quadrature, transforms, differential equations and singular integral equations using orthogonal polynomials. Quadrature based on asymptotics has facilitated optimal complexity quadrature rules, allowing for efficient computation of quadrature rules with millions of nodes. Transforms based on rank structures in change-of-basis operators allow for quasi-optimal complexity, including in multivariate settings such as on triangles and for spherical harmonics. Ordinary and partial differential equations can be solved via sparse linear algebra when set up using orthogonal polynomials as a basis, provided that care is taken with the weights of orthogonality. A similar idea, together with low-rank approximation, gives an efficient method for solving singular integral equations. These techniques can be combined to produce high-performance codes for a wide range of problems that appear in applications.

APA, Harvard, Vancouver, ISO, and other styles

37

Ahmed, Asad, Osman Hasan, Falah Awwad, Nabil Bastaki, and Syed Rafay Hasan. "Formal Asymptotic Analysis of Online Scheduling Algorithms for Plug-In Electric Vehicles’ Charging." Energies 12, no. 1 (December 21, 2018): 19. http://dx.doi.org/10.3390/en12010019.

Full text

Abstract:

A large-scale integration of plug-in electric vehicles (PEVs) into the power grid system has necessitated the design of online scheduling algorithms to accommodate the after-effects of this new type of load, i.e., PEVs, on the overall efficiency of the power system. In online settings, the low computational complexity of the corresponding scheduling algorithms is of paramount importance for the reliable, secure, and efficient operation of the grid system. Generally, the computational complexity of an algorithm is computed using asymptotic analysis. Traditionally, the analysis is performed using the paper-pencil proof method, which is error-prone and thus not suitable for analyzing the mission-critical online scheduling algorithms for PEV charging. To overcome these issues, this paper presents a formal asymptotic analysis approach for online scheduling algorithms for PEV charging using higher-order-logic theorem proving, which is a sound computer-based verification approach. For illustration purposes, we present the complexity analysis of two state-of-the-art online algorithms: the Online cooRdinated CHARging Decision (ORCHARD) algorithm and online Expected Load Flattening (ELF) algorithm.

APA, Harvard, Vancouver, ISO, and other styles

38

Gilman, Jane. "Algorithms, complexity and discreteness criteria in PSL(2, C)." Journal d'Analyse Mathématique 73, no. 1 (December 1997): 91–114. http://dx.doi.org/10.1007/bf02788139.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Kreyndelin, Vitaly B., and Elena D. Grigorieva. "ANALYSIS OF FAST ALGORITHM OF MATRIX-VECTOR MULTIPLICATION FOR THE BANK OF DIGITAL FILTERS." T-Comm 15, no. 1 (2021): 4–10. http://dx.doi.org/10.36724/2072-8735-2021-15-1-4-10.

Full text

Abstract:

Algorithms of implementation of vector-matrix multiplication are presented, which are intended for application in banks (sets) of digital filters. These algorithms provide significant savings in computational costs over traditional algorithms. At the same time, reduction of computational complexity of algorithms is achieved without any performance loss of banks (sets) of digital filters. As the basis for the construction of algorithms proposed in the article, the previously known Winograd method of multiplication of real matrices and vectors and two versions of the method of type 3M for multiplication of complex matrices and vectors are used. Methods of combining these known methods of multiplying matrices and vectors for building digital filter banks (sets) are considered. The analysis of computing complexity of such ways which showed a possibility of reduction of computing complexity in comparison with a traditional algorithm of realization of bank (set) of digital filters approximately in 2.66 times – at realization on the processor without hardware multiplier is carried out; and by 1.33 times – at realization on the processor with the hardware multiplier. These indicators are markedly higher than those of known algorithms. Analysis of sensitivity of algorithms proposed in this article to rounding errors arising by digital signal processing was carried out. Based on this analysis, an algorithm is selected that has a computational complexity smaller than that of a traditional algorithm, but its sensitivity to rounding errors is the same as that of a traditional algorithm. Recommendations are given on its practical application in the development of a bank (set) of digital filters.

APA, Harvard, Vancouver, ISO, and other styles

40

Kim, Bong-seok, Sangdong Kim, Youngseok Jin, and Jonghun Lee. "Low-Complexity Joint Range and Doppler FMCW Radar Algorithm Based on Number of Targets." Sensors 20, no. 1 (December 20, 2019): 51. http://dx.doi.org/10.3390/s20010051.

Full text

Abstract:

A low-complexity joint range and Doppler frequency-modulated continuous wave (FMCW) radar algorithm based on the number of targets is proposed in this paper. This paper introduces two low-complexity FMCW radar algorithms, that is, region of interest (ROI)-based and partial discrete Fourier transform (DFT)-based algorithms. We find the low-complexity condition of each algorithm by analyzing the complexity of these algorithms. From this analysis, it is found that the number of targets is an important factor in determining complexity. Based on this result, the proposed algorithm selects a low-complexity algorithm between two algorithms depending the estimated number of targets and thus achieves lower complexity compared two low-complexity algorithms introduced. The experimental results using real FMCW radar systems show that the proposed algorithm works well in a real environment. Moreover, central process unit time and count of float pointing are shown as a measure of complexity.

APA, Harvard, Vancouver, ISO, and other styles

41

Romaguera, S., P. Tirado, and O. Valero. "New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces." International Journal of Computer Mathematics 89, no. 13-14 (September 2012): 1728–41. http://dx.doi.org/10.1080/00207160.2012.659246.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Selvi, V. "Clustering Analysis of Greedy Heuristic Method in Zero_One Knapsack Problem." International Journal of Emerging Research in Management and Technology 6, no. 7 (June 29, 2018): 39. http://dx.doi.org/10.23956/ijermt.v6i7.181.

Full text

Abstract:

Knapsack problem is a surely understood class of optimization problems, which tries to expand the profit of items in a knapsack without surpassing its capacity, Knapsack can be solved by several algorithms such like Greedy, dynamic programming, Branch & bound etc. The solution to the zero_one knapsack problem (KP) can be viewed as the result of a sequence of decision. Clustering is the process of resolving that type of applications. Different clustering application for grouping elements with equal priority. In this paper we are introducing greedy heuristic algorithm for solving zero_one knapsack problem. We will exhibit a relative investigation of the Greedy, dynamic programming, B&B and Genetic algorithms regarding of the complexity of time requirements, and the required programming efforts and compare the total value for each of them. Greedy and Genetic algorithms can be used to solve the 0-1 Knapsack problem within a reasonable time complexity. The worst-case time complexity (Big-O) of both algorithms is O(N). Using the greedy method, the algorithm can produce high quality clusters while reduce time the best partioning avoid the memory confinement problem during the process.

APA, Harvard, Vancouver, ISO, and other styles

43

Chernov, N., C. Lesort, and N. Simányi. "On the complexity of curve fitting algorithms." Journal of Complexity 20, no. 4 (August 2004): 484–92. http://dx.doi.org/10.1016/j.jco.2004.01.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Ryabko, Boris Ya. "The Complexity and Effectiveness of Prediction Algorithms." Journal of Complexity 10, no. 3 (September 1994): 281–95. http://dx.doi.org/10.1006/jcom.1994.1015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

CLÉMENT, J., T. H. NGUYEN THI, and B. VALLÉE. "Towards a Realistic Analysis of Some Popular Sorting Algorithms." Combinatorics, Probability and Computing 24, no. 1 (December 11, 2014): 104–44. http://dx.doi.org/10.1017/s0963548314000649.

Full text

Abstract:

We describe a general framework for realistic analysis of sorting algorithms, and we apply it to the average-case analysis of three basic sorting algorithms (QuickSort,InsertionSort,BubbleSort). Usually the analysis deals with the mean number of key comparisons, but here we view keys as words produced by the same source, which are compared via their symbols in lexicographic order. The ‘realistic’ cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity ofQuickSortis asymptotic to 2nlogn,InsertionSortton2/4 andBubbleSortton2/2. With respect to symbol comparisons, we prove that their average-case complexity becomes Θ (nlog2n), Θ(n2), Θ (n2logn). In these three cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely entropy and coincidence) with respect to the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

46

Lv, Ming Xia, Yan Kun Lai, and Dong Tang. "Performance Analysis of Low Complexity Multiuser Scheduling Algorithms in MIMO System." Applied Mechanics and Materials 392 (September 2013): 867–71. http://dx.doi.org/10.4028/www.scientific.net/amm.392.867.

Full text

Abstract:

The total throughput of the communication system can be maximized by allocating the common radio resource to the user or the user group having the best channel quality at a given time and the multiuser diversity gain can be obtained when multiple users share the same channel at one time. The object to select the users is to select the users with the maximum sum capacity. As for a scheduling algorithm, exhaustive algorithm can get the largest capability of the system by multi-user scheduling. However, this algorithm is quite complex hence the cost of operation to a base station has substantial increased. We compare the multiuser performance of two fast user selection algorithms with low complexity in MIMO-MRC systems with co-channel interferences. From the simulation results, these two algorithms not only decrease the computational complexity of the scheduling algorithm but also retain large capability of the MIMO system.

APA, Harvard, Vancouver, ISO, and other styles

47

Corus, Dogan, Per Kristian Lehre, Frank Neumann, and Mojgan Pourhassan. "A Parameterised Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms." Evolutionary Computation 24, no. 1 (March 2016): 183–203. http://dx.doi.org/10.1162/evco_a_00147.

Full text

Abstract:

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other’s hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.

APA, Harvard, Vancouver, ISO, and other styles

48

Liu, Ya-Feng, Yu-Hong Dai, and Zhi-Quan Luo. "Coordinated Beamforming for MISO Interference Channel: Complexity Analysis and Efficient Algorithms." IEEE Transactions on Signal Processing 59, no. 3 (March 2011): 1142–57. http://dx.doi.org/10.1109/tsp.2010.2092772.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

He, Jun, and Xin Yao. "Erratum to: Drift analysis and average time complexity of evolutionary algorithms." Artificial Intelligence 140, no. 1-2 (September 2002): 245–48. http://dx.doi.org/10.1016/s0004-3702(02)00260-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Zhang, Junyu, Shiqian Ma, and Shuzhong Zhang. "Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis." Mathematical Programming 184, no. 1-2 (August 10, 2019): 445–90. http://dx.doi.org/10.1007/s10107-019-01418-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic '080201 Analysis of Algorithms and Complexity'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles