Готові списки джерел за темами / Worst-case complexity analysis

Зміст

Статті в журналах
Дисертації
Книги
Частини книг
Тези доповідей конференцій

Добірка наукової літератури з теми "Worst-case complexity analysis"

Автор: Grafiati

Опубліковано: 10 березня 2023

Оновлено: 31 липня 2025

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Worst-case complexity analysis".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

Більше джерел

Дисертації з теми "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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

Книги з теми "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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

Частини книг з теми "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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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.

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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,

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!