检索结果-内蒙古大学图书馆

time complexity of Link Reversal Routing

ACM TRANSACTIONS ON ALGORITHMS 2015年第3期11卷 18-18页

作者： Charron-Bost, Bernadette Fuegger, Matthias Welch, Jennifer L. Widder, Josef Ecole Polytech LIX Lab Informat F-91128 Palaiseau France TU Wien Dept Comp Engn A-1040 Vienna Austria Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA TU Wien A-1040 Vienna Austria

Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing and subsequently applied to other problems including mutual exclusion, leader election, and resource allocation. Although these algorithms are well known, until now there have been only preliminary results on time complexity, even for the simplest link reversal algorithm for routing, called Full Reversal. In Full Reversal, a sink reverses all its incident links, whereas in other link reversal algorithms (e.g., Partial Reversal), a sink reverses only some of its incident links. Charron-Bost et al. introduced a generalization, called LR, that includes Full and Partial Reversal as special cases. In this article, we present an exact expression for the time complexity of LR. The expression is stated in terms of simple properties of the initial graph. The result specializes to exact formulas for the time complexity of any node in any initial acyclic directed graph for both Full and Partial Reversal. Having the exact formulas provides insight into the behavior of Full and Partial Reversal on specific graph families. Our first technical insight is to describe the behavior of Full Reversal as a dynamical system and to observe that this system is linear in min-plus algebra. Our second technical insight is to overcome the difficulty posed by the fact that LR is not linear by transforming every execution of LR from an initial graph into an execution of Full Reversal from a different initial graph while maintaining the execution's work and time complexity.

关键词： Routing link reversal time complexity linear dynamical systems min-plus algebra

来源：评论

学校读者我要写书评

暂无评论

The time complexity Analysis of Neural Network Model Configurations 2

The Time Complexity Analysis of Neural Network Model Configu...

引用

2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE)

作者： Lee, Rich Chen, Ing-Yi Natl Taipei Univ Technol Dept Comp Sci & Informat Engn 1Sec 3Zhongxiao E Rd Taipei Taiwan

ISBN: (纸本)9781728166957

The neural network algorithms, such as the deep-learning approach, have been widely applied in dealing with the computer vision problems. The more sophisticated the neural network model is designed;the more computing resources and processing time will be consumed. The time-complexity analysis discloses the training and validating time processed versus the accuracy outcome of the neural network model. This paper proposes a rigorous framework of conducting the time-complexity analysis against the neural network models. From the experiment results against the progressively sophisticated neural network model design, the paper argues that pursuing an unreasonably high accurate result or in persisting in finding the perfect algorithm may not be worth and in practical from the time-complexity perspective if the data quality was not consistently in favor of the algorithm chosen.

关键词： Computer Vision Deep Learning Image Classification Ensemble Methods time complexity

来源：评论

学校读者我要写书评

暂无评论

A Practical Approach to the time complexity of Algorithms 29

A Practical Approach to the Time Complexity of Algorithms

引用

29th Annual Conference of the European-Association-for-Education-in-Electrical-and-Information-Engineering (EAEEIE)

作者： Hynek, Josef Univ Hradec Kralove Fac Informat & Management Hradec Kralove Czech Republic

ISBN: (纸本)9781728132228

Rapid development of information technology brings along the constant need for inclusion of new and attractive modules into ICT specialist curricula and there quite common attempts to reduce less attractive parts of ICT curricula and, unfortunately, theoretical subjects are very often among the candidates for possible cuts or even replacements by something more applicable. We believe that the theoretical foundations of computer science are very important and that there is a possibility to persuade our students that they must be aware of the theoretical principles in order to become a real specialist in this field. This paper describes our approach taken to teaching the module of algorithms complexity with a special focus on the types of practical examples utilized to demonstrate the usefulness and applicability of the theory of algorithms complexity.

关键词： algorithms time complexity ICT curricula design practical examples

来源：评论

学校读者我要写书评

暂无评论

O-Charts: Towards an Effective Toolkit for Teaching time complexity 45

O-Charts: Towards an Effective Toolkit for Teaching Time Com...

引用

45th Annual Frontiers in Education Conference (FIE)

作者： Barlowe, Scott Scott, Andrew Western Carolina Univ Dept Math & Comp Sci Cullowhee NC 28723 USA

ISBN: (纸本)9781479984541

Scientists, business analysts, and others in a growing number of fields are trying to cope with the vast amount of data being generated. The lack of software that can efficiently process large data sets hinders insight into complex relationships. One of the most important concepts in learning how to construct efficient code is time complexity analysis with Big-O notation. Students often find time complexity difficult to learn and too abstract to apply in any meaningful way. Common instructional methods consist of a combination of mathematics and intuitive analysis which are often too cumbersome for practical application or cannot be extended to complex algorithms. Unfortunately, there are few tools available for teaching time complexity that students find concrete, straightforward, and applicable to real problems. In this paper, we present O-Charts, a first step in the development of a practical toolkit for teaching and applying time complexity analysis. O-Charts allow the systematic analysis of deeply nested loops where the use of control variables makes the number of executions difficult to define, calculate, and explain. We report initial results and our plans for future work.

关键词： Algorithm design and analysis Concrete Data structures Education time complexity Upper bound complexity classes Algorithm design and analysis Data structures Upper bound Concrete Education Number field tool cases Pedagogy Teaching

来源：评论

学校读者我要写书评

暂无评论

time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2022年 471卷

作者： Jin, Shi Liu, Nana Yu, Yue Shanghai Jiao Tong Univ Inst Nat Sci Sch Math Sci MOE LSC Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Inst Nat Sci Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Key Lab Sci & Engn Comp Minist Educ Shanghai 200240 Peoples R China Univ Michigan Shanghai Jiao Tong Univ Joint Inst Shanghai 200240 Peoples R China

We investigate time complexities of finite difference methods for solving the high -dimensional linear heat equation, the high-dimensional linear hyperbolic equation and the multiscale hyperbolic heat system with quantum algorithms (hence referred to as the "quantum difference methods"). For the heat and linear hyperbolic equations we study the impact of explicit and implicit time discretizations on quantum advantages over the classical difference method. For the multiscale problem, we find the time complexity of both the classical treatment and quantum treatment for the explicit scheme scales as O(1/epsilon), where epsilon is the scaling parameter, while the scaling for the multiscale Asymptotic -Preserving (AP) schemes does not depend on epsilon. This indicates that it is still of great importance to develop AP schemes for multiscale problems in quantum computing.(c) 2022 Elsevier Inc. All rights reserved.

关键词： Quantum difference methods Quantum linear systems algorithms HHL algorithm time complexity Asymptotic -preserving schemes

来源：评论

学校读者我要写书评

暂无评论

time complexity evaluation of cover song identification algorithms

引用

APPLIED ACOUSTICS 2021年 175卷 107777-107777页

作者： Ferreira, Martha Dais de Mello, Rodrigo Fernandes Dalhousie Univ Fac Comp Sci Halifax NS Canada Univ Sao Paulo Inst Math & Comp Sci Sao Carlos SP Brazil

Cover Song Identification (CSI) is a task in Music Information Retrieval (MIR) that attempts to identify other versions of a song containing different structures, tonalities, and tempos, what brings several challenges to this task. Some of frameworks proposed to identify cover songs were evaluated through the Music Information Retrieval Evaluation eXchange (MIREX) competition that aims to assess algorithms for MIR tasks. Among the problems faced by researchers is the time complexity of the algorithms considered in the context of CSI, what limits or makes unfeasible their application in real-world scenarios. Considering this challenge, we present a time complexity evaluation of the two most popular frameworks presented and ranked at the MIREX competition. This assessment confirms both algorithms have the same worst-case scenario of O(n(2)), besides a significant difference in terms of their constants, which impact in overall processing time. Finally, this analysis can support researchers to improve algorithms for the CSI task, thus leading to more suitable frameworks for real-world scenarios. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Cover song identification time complexity MIREX Music information retrieval Algorithms

来源：评论

学校读者我要写书评

暂无评论

Hybrid Dynamical Evolutionary Algorithm and time complexity Analysis

Hybrid Dynamical Evolutionary Algorithm and Time Complexity ...

引用

International Conference on Information Technology and Management Innovation (ICITMI2012)

作者： Li, Huiying Zhang, Yilai Xu, Xing Jingdezhen Ceram Inst Sch Informat Engn Jingdezhen Peoples R China

ISBN: (纸本)9783037855744

The dynamical evolutionary algorithm (DEA) is a new evolutionary algorithm based on the theory of statistical mechanics, however, DEA converges slowly and often converge at local optima for some function optimization problems. In this paper, a hybrid dynamical evolutionary algorithm (HDEA) with multi-parent crossover and differential evolution mutation is proposed for accelerating convergence velocity and easily escaping suboptimal solutions. Moreover, the population of HDEA is initialized by chaos. In order to confirm the effectiveness of our algorithm, HDEA is applied to solve the typical numerical function minimization problems. The computational complexity of HDEA is analyzed, and the experimental results show that HDEA outperforms the DEA in the aspect of convergence velocity and precision, even the two algorithms have the similar time complexity.

关键词： dynamical evolutionary algorithm chaos multi-parent crossover differential evolution time complexity

来源：评论

学校读者我要写书评

暂无评论

Hybrid Approach to Reduce time complexity of String Matching Algorithm Using Hashing with Chaining

Hybrid Approach to Reduce Time Complexity of String Matching...

引用

International Conference on Information and Communication Technology for Sustainable Development (ICT4SD)

作者： Pandey, Shivendra Kumar Tiwari, Hari Krishna Tripathi, Priyanka Natl Inst Tech Teachers Training & Res Dept Comp Applicat & Res Bhopal India

ISBN: (纸本)9789811001291;9789811001277

String matching is an integral part of various important areas of computer science viz search engines, DNA matching, information retrieval, security, and biological systems. String matching algorithms are used in finding a pattern in a string. In this paper, the authors have given a novel algorithm to reduce the time complexity of string matching. The proposed algorithm is based on the concept of hashing with chaining. Further, the authors have found reduced time complexity in most of the cases and equal in few.

关键词： String matching Hashing Chaining time complexity

来源：评论

学校读者我要写书评

暂无评论

On time complexity analysis of algorithms

On time complexity analysis of algorithms

引用

9th World Multi-Conference on Systemics, Cybernetics and Informatics

作者： Tarek, Ahmed Eastern Kentucky Univ Dept Comp Sci Richmond KY 40475 USA

ISBN: (纸本)9789806560550

There exists a variety of techniques for the time complexity analysis of algorithms and functions. This analysis is used to find out the upper-bound on time complexity in big-oh notation, which is denoted by O(g(n)) with g(n) is a function of n, and n is the size of the given problem. Besides the big-oh complexity, there axe other complexity notations, such as Omega, theta, and small o complexities. complexity analysis is used to select an appropriate algorithm for solving a given problem using computers. Unfortunately there does not exist any efficient, generalized framework for the time complexity analysis. Most of the existing techniques are complex, obsolete, and hard to use in practice. There is a misconception in some literature that 0(g(n)) is a function rather than a set. In this paper, it has been established that 0(g(n) is basically a set, which includes all algorithms with an upper bound on the order of g(n). Moreover, a generalized framework for analyzing the time-complexity function f (n) for algorithms in obtaining the big-oh notational complexity has been proposed. The method has been extended for functions f (n(1), n(2), ... , n(m)), m = 1, 2, ... involving multiple variables. Other complexity orders are discussed, and compared with the big-oh complexity.

关键词： time complexity complexity function big-oh notation complexity order algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Empirical time complexity of Generic Dijkstra Algorithm 17

Empirical Time Complexity of Generic Dijkstra Algorithm

引用

IFIP/IEEE International Symposium on Integrated Network Management (IM)

作者： Jurkiewicz, Piotr Biernacka, Edyta Domzal, Jerzy Wojcik, Robert AGH Univ Sci & Technol Dept Telecommun Krakow Poland

ISBN: (纸本)9783903176324

Generic Dijkstra is a novel algorithm for finding the optimal shortest path in both wavelength-division multiplexed networks (WDM) and elastic optical networks (EON), claimed to outperform known algorithms considerably. Because of its novelty, it has not been independently implemented and verified. Its time complexity also remains unknown. In this paper, we perform run-time analysis and show that Generic Dijkstra running time grows quadratically with the number of graph vertices and logarithmically with the number of edge units. We also discover that the running time of the Generic Dijkstra algorithm in the function of network utilization is not monotonic, as peak running time is at approximately 0.25 network utilization. Additionally, we provide an independent open source implementation of Generic Dijkstra in the Python language. We confirm the correctness of the algorithm and its superior performance. In comparison to the Filtered Graphs algorithm, Generic Dijkstra is approximately 2.3 times faster in networks with 25 to 500 nodes, and in 90% of calls its computation takes less time.

关键词： elastic optical networks EON time complexity RWA RSA RMSA

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：