Bibliografías temáticas / Worst-case complexity analysis

Índice

Artículos de revistas
Tesis
Libros
Capítulos de libros
Actas de conferencias

Literatura académica sobre el tema "Worst-case complexity analysis"

Autor: Grafiati

Publicado: 10 de marzo de 2023

Última modificación: 31 de julio de 2025

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Worst-case complexity analysis".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Artículos de revistas sobre el tema "Worst-case complexity analysis"

Szirmay-Kalos, L., and G. Márton. "Worst-case versus average case complexity of ray-shooting." Computing 61, no. 2 (1998): 103–31. http://dx.doi.org/10.1007/bf02684409.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Kwas, Marek, and Youming Li. "Worst case complexity of multivariate Feynman–Kac path integration." Journal of Complexity 19, no. 6 (2003): 730–43. http://dx.doi.org/10.1016/s0885-064x(03)00048-7.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Jackowski, Tomasz. "Complexity of multilinear problems in the worst case setting." Journal of Complexity 6, no. 4 (1990): 389–408. http://dx.doi.org/10.1016/0885-064x(90)90030-h.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Milanese, M., and A. Vicino. "Information-Based Complexity and Nonparametric Worst-Case System Identification." Journal of Complexity 9, no. 4 (1993): 427–46. http://dx.doi.org/10.1006/jcom.1993.1028.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Plaskota, Leszek. "Worst Case Complexity of Problems with Random Information Noise." Journal of Complexity 12, no. 4 (1996): 416–39. http://dx.doi.org/10.1006/jcom.1996.0026.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Pemmaraju, Sriram V., and Clifford A. Shaffer. "Analysis of the worst case space complexity of a PR quadtree." Information Processing Letters 49, no. 5 (1994): 263–67. http://dx.doi.org/10.1016/0020-0190(94)90065-5.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Li, Youming, and Grzegorz W. Wasilkowski. "Worst Case Complexity of Weighted Approximation and Integration over Rd." Journal of Complexity 18, no. 1 (2002): 330–45. http://dx.doi.org/10.1006/jcom.2001.0632.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Kumar, Pijush Kanti. "Breaking the O(n^2) Barrier: Novel Approaches to Time Complexity Analysis in Quick Sort." International Journal of Computer Science and Mobile Computing 9, no. 11 (2020): 107–17. http://dx.doi.org/10.47760/ijcsmc.2020.v09i11.010.

Texto completo

Resumen

The most common type of sorting algorithm used is quicksort. As the name suggests it is the one of the most fastest sorting algorithm used since the innovation of sorting. However, this sort has often been criticised for its worst-case time complexity that is O(n^2). Practically the quick sort tends to follow its average case and best-case scenarios most of the time. So practically the quick sort is the most efficient practical sorting algorithm. In this paper we will fine tune this algorithm and remove its worst-case time complexity of O(n^2) and make this the best sorting algorithm both theo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Short, Michael. "Bounds on Worst-Case Deadline Failure Probabilities in Controller Area Networks." Journal of Computer Networks and Communications 2016 (2016): 1–12. http://dx.doi.org/10.1155/2016/5196092.

Texto completo

Resumen

Industrial communication networks like the Controller Area Network (CAN) are often required to operate reliably in harsh environments which expose the communication network to random errors. Probabilistic schedulability analysis can employ rich stochastic error models to capture random error behaviors, but this is most often at the expense of increased analysis complexity. In this paper, an efficient method (of time complexityO(n log n)) to bound the message deadline failure probabilities for an industrial CAN network consisting ofnperiodic/sporadic message transmissions is proposed. The paper

Los estilos APA, Harvard, Vancouver, ISO, etc.

De Haan, Ronald, Anna Roubickova, and Stefan Szeider. "Parameterized Complexity Results for Plan Reuse." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (2013): 224–31. http://dx.doi.org/10.1609/aaai.v27i1.8655.

Texto completo

Resumen

Planning is a notoriously difficult computational problem of high worst-case complexity. Researchers have been investing significant efforts to develop heuristics or restrictions to make planning practically feasible. Case-based planning is a heuristic approach where one tries to reuse previous experience when solving similar problems in order to avoid some of the planning effort. Plan reuse may offer an interesting alternative to plan generation in some settings. We provide theoretical results that identify situations in which plan reuse is provably tractable. We perform our analysis in the f

Los estilos APA, Harvard, Vancouver, ISO, etc.

Más fuentes

Tesis sobre el tema "Worst-case complexity analysis"

Panigrahi, Sunil Kumar, Soubhik Chakraborty, and Jibitesh Mishra. "A Statistical Analysis of Bubble Sort in terms of Serial and Parallel Computation." IJCSN Journal, 2012. http://hdl.handle.net/10150/214089.

Texto completo

Resumen

In some recent papers, the weight based statistical bounds have arguably explained time complexity better than the count based mathematical bounds. This is definitely true for average case where for an arbitrary code it is difficult to identify the pivotal operation or pivotal region in the code for taking the expectation and/or when the probability distribution, over which expectation is taken, becomes unrealistic over the problem domain. In worst case, it can certify whether a mathematical bound is conservative or not. Here we revisit the results on Bubble sort in sequential mode an

Los estilos APA, Harvard, Vancouver, ISO, etc.

Gurioli, Gianmarco. "Adaptive Regularisation Methods under Inexact Evaluations for Nonconvex Optimisation and Machine Learning Applications." Doctoral thesis, 2021. http://hdl.handle.net/2158/1238314.

Texto completo

Resumen

The major aim of this research thesis is to handle two main challenges arising when solving unconstrained optimisation problems with second-order methods: the reduction of the per-iteration cost and the stochastic analysis of the resulting non- deterministic algorithms. This is motivated by the fact that second-order procedures can be more efficient than first-order ones on badly scaled and ill-conditioned problems, since they seem to potentially take advantage of curvature information to easier escape from saddle points, being more robust to the choice of hyperparameters and the parameters tu

Los estilos APA, Harvard, Vancouver, ISO, etc.

Libros sobre el tema "Worst-case complexity analysis"

Kowalski, Marek A., Krzystof A. Sikorski, and Frank Stenger. Selected Topics in Approximation and Computation. Oxford University Press, 1995. http://dx.doi.org/10.1093/oso/9780195080599.001.0001.

Texto completo

Resumen

Selected Topics in Approximation and Computation addresses the relationship between modern approximation theory and computational methods. The text is a combination of expositions of basic classical methods of approximation leading to popular splines and new explicit tools of computation, including Sinc methods, elliptic function methods, and positive operator approximation methods. It also provides an excellent summary of worst case analysis in information based complexity. It relates optimal computational methods with the theory of s-numbers and n-widths. It can serve as a text for senior-gr

Los estilos APA, Harvard, Vancouver, ISO, etc.

Capítulos de libros sobre el tema "Worst-case complexity analysis"

Xia, Lirong, and Weiqiang Zheng. "Beyond the Worst Case: Semi-random Complexity Analysis of Winner Determination." In Web and Internet Economics. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-22832-2_19.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Haslbeck, Maximilian P. L., and Peter Lammich. "For a Few Dollars More." In Programming Languages and Systems. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-72019-3_11.

Texto completo

Resumen

AbstractWe present a framework to verify both, functional correctness and worst-case complexity of practically efficient algorithms. We implemented a stepwise refinement approach, using the novel concept of resource currencies to naturally structure the resource analysis along the refinement chain, and allow a fine-grained analysis of operation counts. Our framework targets the LLVM intermediate representation. We extend its semantics from earlier work with a cost model. As case study, we verify the correctness and $$O(n\log n)$$ O ( n log n ) worst-case complexity of an implementation of the

Los estilos APA, Harvard, Vancouver, ISO, etc.

Benerecetti, Massimo, Daniele Dell’Erba, and Fabio Mogavero. "Solving Mean-Payoff Games via Quasi Dominions." In Tools and Algorithms for the Construction and Analysis of Systems. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-45237-7_18.

Texto completo

Resumen

Abstract We propose a novel algorithm for the solution of mean-payoff games that merges together two seemingly unrelated concepts introduced in the context of parity games, small progress measures and quasi dominions. We show that the integration of the two notions can be highly beneficial and significantly speeds up convergence to the problem solution. Experiments show that the resulting algorithm performs orders of magnitude better than the asymptotically-best solution algorithm currently known, without sacrificing on the worst-case complexity.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Aggarwal, Saksham, Alejandro Stuckey de la Banda, Luke Yang, and Julian Gutierrez. "A Matrix-Based Approach to Parity Games." In Tools and Algorithms for the Construction and Analysis of Systems. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30823-9_34.

Texto completo

Resumen

AbstractParity games are two-player zero-sum games of infinite duration played on finite graphs for which no solution in polynomial time is still known. Solving a parity game is an $$\text{ NP }\cap \text{ co-NP }$$ NP ∩ co-NP problem, with the best worst-case complexity algorithms available in the literature running in quasi-polynomial time. Given the importance of parity games within automated formal verification, several practical solutions have been explored showing that considerably large parity games can be solved somewhat efficiently. Here, we propose a new approach to solving parity ga

Los estilos APA, Harvard, Vancouver, ISO, etc.

Schmid, Stefan, Nicolas Schnepf, and Jiří Srba. "Resilient Capacity-Aware Routing." In Tools and Algorithms for the Construction and Analysis of Systems. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-72016-2_22.

Texto completo

Resumen

AbstractTo ensure a high availability, communication networks provide resilient routing mechanisms that quickly change routes upon failures. However, a fundamental algorithmic question underlying such mechanisms is hardly understood: how to verify whether a given network reroutes flows along feasible paths, without violating capacity constraints, for up to k link failures? We chart the algorithmic complexity landscape of resilient routing under link failures, considering shortest path routing based on link weights as e.g. deployed in the ECMP protocol. We study two models: a pessimistic model

Los estilos APA, Harvard, Vancouver, ISO, etc.

Balachander, Mrudula, Emmanuel Filiot, and Jean-François Raskin. "LTL Reactive Synthesis with a Few Hints." In Tools and Algorithms for the Construction and Analysis of Systems. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30820-8_20.

Texto completo

Resumen

AbstractWe study a variant of the problem of synthesizing Mealy machines that enforce LTL specifications against all possible behaviours of the environment, including hostile ones. In the variant studied here, the user provides the high level LTL specification $$\varphi $$ φ of the system to design, and a set E of examples of executions that the solution must produce. Our synthesis algorithm first generalizes the user-provided examples in E using tailored extensions of automata learning algorithms, while preserving realizability of $$\varphi $$ φ . Second, it turns the (usually) incomplete Mea

Los estilos APA, Harvard, Vancouver, ISO, etc.

Albert, Elvira, Samir Genaim, Enrique Martin-Martin, Alicia Merayo, and Albert Rubio. "Lower-Bound Synthesis Using Loop Specialization and Max-SMT." In Computer Aided Verification. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81688-9_40.

Texto completo

Resumen

AbstractThis paper presents a new framework to synthesize lower-bounds on the worst-case cost for non-deterministic integer loops. As in previous approaches, the analysis searches for a metering function that under-approximates the number of loop iterations. The key novelty of our framework is the specialization of loops, which is achieved by restricting their enabled transitions to a subset of the inputs combined with the narrowing of their transition scopes. Specialization allows us to find metering functions for complex loops that could not be handled before or be more precise than previous

Los estilos APA, Harvard, Vancouver, ISO, etc.

Cocco, Simona, and Rémi Monasson. "Analyzing Search Algorithms with Physical Methods." In Computational Complexity and Statistical Physics. Oxford University Press, 2005. http://dx.doi.org/10.1093/oso/9780195177374.003.0010.

Texto completo

Resumen

The computational effort needed to deal with large combinatorial structures varies considerably with the task to be performed and the resolution procedure used [425]. The worst-case complexity of a decision or optimization problem is defined as the time required by the best algorithm to treat any possible input to the problem. For instance, the worst-case complexity of the problem of sorting a list of n numbers scales as n log n: there exist several algorithms that can order any list in at most ~ n log n elementary operations, and none with asymptotically fewer operations. Unfortunately, the w

Los estilos APA, Harvard, Vancouver, ISO, etc.

Sikorski, Krzysztof A. "Fixed Points- Noncontractive Functions." In Optimal Solution of Nonlinear Equations. Oxford University Press, 2001. http://dx.doi.org/10.1093/oso/9780195106909.003.0007.

Texto completo

Resumen

In this chapter we consider the approximation of fixed points of noncontractive functions with respect to the absolute error criterion. In this case the functions may have multiple and/or whole manifolds of fixed points. We analyze methods based on sequential function evaluations as information. The simple iteration usually does not converge in this case, and the problem becomes much more difficult to solve. We prove that even in the two-dimensional case the problem has infinite worst case complexity. This means that no methods exist that solve the problem with arbitrarily small error toleranc

Los estilos APA, Harvard, Vancouver, ISO, etc.

Smith, Justin R. "VII.Probabilistic Algorithms." In The Design and Analysis of Parallel Algorithms. Oxford University PressNew York, NY, 1993. http://dx.doi.org/10.1093/oso/9780195078817.003.0031.

Texto completo

Resumen

Abstract Numerical algorithms. The Buffon Needle algorithm falls into this category. These algorithms involve performing a large number of independent trials and produce an answer that converges to the correct answer as the number of trials increase. They are ideally suited to parallelization, since the trials are completely independent These are algorithms that always work, and always produce correct answers, but the running time is indeterminate, as a result of random choices they make. In this case, the probable running time may be very fast, but the worst case running time (as a result of

Los estilos APA, Harvard, Vancouver, ISO, etc.

Actas de conferencias sobre el tema "Worst-case complexity analysis"

Marchetti-Spaccamella, A., A. Pelaggi, and D. Sacca. "Worst-case complexity analysis of methods for logic query implementation." In the sixth ACM SIGACT-SIGMOD-SIGART symposium. ACM Press, 1987. http://dx.doi.org/10.1145/28659.28691.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Said, Amir. "Worst-case Analysis of the Low-complexity Symbol Grouping Coding Technique." In 2006 IEEE International Symposium on Information Theory. IEEE, 2006. http://dx.doi.org/10.1109/isit.2006.262028.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Wieder, Alexander, and Bjorn B. Brandenburg. "On the Complexity of Worst-Case Blocking Analysis of Nested Critical Sections." In 2014 IEEE Real-Time Systems Symposium (RTSS). IEEE, 2014. http://dx.doi.org/10.1109/rtss.2014.34.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Necoara, Ion. "Worst-case computational complexity analysis for embedded MPC based on dual gradient method." In 2014 18th International Conference on System Theory, Control and Computing (ICSTCC). IEEE, 2014. http://dx.doi.org/10.1109/icstcc.2014.6982477.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Shi, Ziqiang, and Rujie Liu. "Better Worst-Case Complexity Analysis of the Block Coordinate Descent Method for Large Scale Machine Learning." In 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, 2017. http://dx.doi.org/10.1109/icmla.2017.00-43.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Hausladen, Jürgen, Florian Gerstmayer, Thomas Jerabek, and Martin Horauer. "Integration of Static Worst-Case Execution Time and Stack Usage Analysis for Embedded Systems Software in a Cloud-Based Development Environment." In ASME 2017 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2017. http://dx.doi.org/10.1115/detc2017-67402.

Texto completo

Resumen

New applications relying on embedded systems technologies often come with an increased number of features and functionalities. For instance, improved safety, reliability, usability or reduced power consumption are commonly encountered aspects. Those in turn, however, come usually at the cost of increased complexity. Managing the latter can become challenging, especially when looking at (worst-case) execution times or memory usage of embedded systems. In particular, many applications, e.g., safety-critical or real-time applications, require knowledge about the worst-case execution time and stac

Los estilos APA, Harvard, Vancouver, ISO, etc.

Regli, William C., Satyandra K. Gupta, and Dana S. Nau. "Feature Recognition for Manufacturability Analysis." In ASME 1994 International Computers in Engineering Conference and Exhibition and the ASME 1994 8th Annual Database Symposium collocated with the ASME 1994 Design Technical Conferences. American Society of Mechanical Engineers, 1994. http://dx.doi.org/10.1115/cie1994-0391.

Texto completo

Resumen

Abstract While automated recognition of features has been attempted for a wide range of applications, no single existing approach possesses the functionality required to perform manufacturability analysis. In this paper, we present a methodology for taking a CAD model of a part and extracting a set of machinable features that contains the complete set of alternative interpretations of the part as collections of MRSEVs (Material Removal Shape Element Volumes, a STEP-based library of machining features). The approach handles a variety of features including those describing holes, pockets, slots,

Los estilos APA, Harvard, Vancouver, ISO, etc.

Walker, Mark, and Pavel Y. Tabakov. "Design Optimization of Anisotropic Pressure Vessels With Manufacturing Uncertainties Accounted For." In ASME 8th Biennial Conference on Engineering Systems Design and Analysis. ASMEDC, 2006. http://dx.doi.org/10.1115/esda2006-95767.

Texto completo

Resumen

Accurate optimal design solutions for most engineering structures present considerable difficulties due to the complexity and multi-modality of the functional design space. The situation is made even more complex when potential manufacturing tolerances must be accounted for in the optimizing process. The present study provides an in-depth analysis of the problem and then a technique for determining the optimal design of engineering structures, with manufacturing tolerances accounted for, is proposed and demonstrated. The numerical examples used to demonstrate the technique involve the design o

Los estilos APA, Harvard, Vancouver, ISO, etc.

Tasora, Alessandro, and Dan Negrut. "On Some Properties of the Mechanical Topology That Affect Parallel Solvers." In ASME 2013 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2013. http://dx.doi.org/10.1115/detc2013-13201.

Texto completo

Resumen

The efficiency of parallel solvers for large multibody systems is affected by the topology of the network of constraints. In the most general setting, that is the case of problems involving contacts between large numbers of parts, the mechanical topology cannot be predicted a priori and also changes during the simulation. Depending on the strategy for splitting the computational workload on the processing units, different types of worst case scenarios can happen. In this paper we discuss a few approaches to the parallelization of multibody solvers, ranging from the fine-grained parallism on GP

Los estilos APA, Harvard, Vancouver, ISO, etc.

Nicak, Tomas, Herbert Schendzielorz, and Elisabeth Keim. "Analysis of Fracture Mechanics Specimens Made of Inconel 600 Based on Assessment Methods of Different Complexity." In ASME 2009 Pressure Vessels and Piping Conference. ASMEDC, 2009. http://dx.doi.org/10.1115/pvp2009-77195.

Texto completo

Resumen

Fracture mechanics analysis plays an important role in the frame of the safety assessment of nuclear components. Usually the goal of such an analysis is to decide if a given flaw size in the piping (or any component of the primary circuit) is acceptable or not. The word “acceptable” means that structural integrity of the component is guaranteed with sufficient safety margins up to the end of service life or up to the next in-service inspection (considering the worst case loads and lower bound material properties). To fulfil this high-responsible task in practice some useful Engineering Assessm

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!